Greedy interval scheduling and exchange proof
To maximize the number of compatible intervals, repeatedly take the available interval finishing earliest and discard overlapping intervals.
Key knowledge
To maximize the number of compatible intervals, repeatedly take the available interval finishing earliest and discard overlapping intervals. Replacing an optimum's first interval by this choice cannot reduce the feasible remainder, giving the exchange proof. Sorting by finish time yields O(n log n) time.
Conditions and scope
- Intervals are unweighted; use one explicit endpoint-compatibility convention.
- Maximizing total weight requires a different method; local greedy choices are not generally optimal.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Lecture 2 section 2.2 earliest-finishing rule and exchange argument.
2026-10-10 · Independent AI editorial review: All241 compact claims, hypotheses, displayed equations/conventions and all596 origin semantic links read; entire241-entry author exact-source inspection matrix and declared limitations reviewed. Prior105 actual inherited Mathematics/Information records read for whole-inventory breadth. Targeted independent primary sections are listed below; this does NOT claim every cited source body or every proof was independently re-read. This is AI reference-content review, not human disciplinary certification, exhaustive textbook reproduction or experimental replication. Receipt: mathematics-information-independent-content-review.1.
Entry details
Permanent link to this entry ↗- Record identity
- info-greedy-interval-scheduling
- Revision
- university-core.1
- Structured reference record
- University core expansion