Intervals and Greedy Choices
Put every interval on a timeline, one per row, and the classic greedy problems become visible. To fit as many non-overlapping intervals as possible, sort by finish time and keep whatever starts after the last one you kept ended: finishing early leaves the most room for the rest, and no other choice can beat it. To count the rooms a set of meetings needs, sweep the timeline and count how many are open at once; the peak is the answer, because that many overlap at that moment. Assigning rooms is the same sweep with a twist: each meeting takes the first room that is free by its start.
How many rooms do 6 meetings need? Sweep time from left to right. A meeting that starts takes a room, one that ends gives it back, and the most rooms ever taken at once is the answer. Rows are sorted by start; at equal times an end is processed before a start.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 12, with their answers.
Next event at t = 0: a starts. Open meetings go to?
Answer: 1. A start adds one.
Next event at t = 1: b starts. Open meetings go to?
Answer: 2. A start adds one.
Next event at t = 2: c starts. Open meetings go to?
Answer: 3. A start adds one.
Next event at t = 3: a ends. Open meetings go to?
Answer: 2. An end subtracts one.
Next event at t = 4: b ends. Open meetings go to?
Answer: 1. An end subtracts one.
Next event at t = 4: d starts. Open meetings go to?
Answer: 2. A start adds one.
Next event at t = 5: e starts. Open meetings go to?
Answer: 3. A start adds one.
Next event at t = 6: c ends. Open meetings go to?
Answer: 2. An end subtracts one.
Next event at t = 7: d ends. Open meetings go to?
Answer: 1. An end subtracts one.
Next event at t = 8: f starts. Open meetings go to?
Answer: 2. A start adds one.
Next event at t = 9: e ends. Open meetings go to?
Answer: 1. An end subtracts one.
Next event at t = 11: f ends. Open meetings go to?
Answer: 0. An end subtracts one.
How it runs, step by step
How many rooms do 6 meetings need? Sweep time from left to right. A meeting that starts takes a room, one that ends gives it back, and the most rooms ever taken at once is the answer. Rows are sorted by start; at equal times an end is processed before a start.
Sweep over 6 intervals.
t = 0: a starts, taking a room. Open meetings: 1. That is a new maximum, so at least 1 rooms are needed.
Time 0, a starts, 1 open.
t = 1: b starts, taking a room. Open meetings: 2. That is a new maximum, so at least 2 rooms are needed.
Time 1, b starts, 2 open.
t = 2: c starts, taking a room. Open meetings: 3. That is a new maximum, so at least 3 rooms are needed.
Time 2, c starts, 3 open.
t = 3: a ends, freeing a room. Open meetings: 2.
Time 3, a ends, 2 open.
t = 4: b ends, freeing a room. Open meetings: 1.
Time 4, b ends, 1 open.
t = 4: d starts, taking a room. Open meetings: 2.
Time 4, d starts, 2 open.
t = 5: e starts, taking a room. Open meetings: 3.
Time 5, e starts, 3 open.
t = 6: c ends, freeing a room. Open meetings: 2.
Time 6, c ends, 2 open.
t = 7: d ends, freeing a room. Open meetings: 1.
Time 7, d ends, 1 open.
t = 8: f starts, taking a room. Open meetings: 2.
Time 8, f starts, 2 open.
t = 9: e ends, freeing a room. Open meetings: 1.
Time 9, e ends, 1 open.
t = 11: f ends, freeing a room. Open meetings: 0.
Time 11, f ends, 0 open.
3 rooms. At the peak 3 meetings overlapped, so fewer rooms cannot work, and the sweep never needs more than the peak. Sorting the 2n endpoints dominates: O(n log n).
3 rooms needed.
Remember
- Interval scheduling: sort by finish time, keep each interval that starts at or after the last kept end.
- Meeting rooms: sweep sorted endpoints, +1 on a start and -1 on an end; the peak count is the answer.
- Ends sort before starts at the same time, so a room freed at t can be reused at t.
Topics covered
Where this is used
CompilersRegister allocation in compilers
A compiler lays the instructions out in a line and gives every value a live interval covering the stretch where it is still needed. The number of registers a program wants at a point is the number of live intervals overlapping there, so the meeting rooms question is literally the register question, and linear scan assigns each interval the first register free at its start, exactly like partition. HotSpot's C1 JIT allocates this way; when no register is free the value spills to memory, which is the case where you would have to open another room.
DatabasesExclusion constraints on range types
PostgreSQL stores a booking as a single tsrange column and an exclusion constraint rejects any insert whose range overlaps an existing one for the same room. The overlap test runs against a GiST index, so the check stays fast instead of scanning every other booking. This moves the no-two-intervals-overlap invariant out of application code and into the database, where two concurrent bookings for the same slot cannot both win.
BioinformaticsGenome interval tools
A BED file is nothing but intervals on a chromosome, stored half-open exactly like the convention this lesson uses. bedtools merge requires input presorted by chromosome and start, because it collapses overlapping features in a single forward pass. bedtools intersect does not require sorting by default; it loads one file into an in-memory R-tree instead, and the -sorted flag switches it to the same streaming sweep, which is what keeps memory flat on huge files. On a file with tens of millions of aligned reads, that is the difference between holding one cursor per file and holding the whole file in memory.
Operating systemsDeadline scheduling in the Linux kernel
SCHED_DEADLINE runs whichever runnable task has the nearest absolute deadline, the same greedy shape as taking the earliest finish, and on a single CPU that rule is optimal by an exchange argument: if any order meets every deadline then this one does. The kernel also refuses to admit a task whose bandwidth would push the sum of runtime over period past the capacity it accounts for, which by default is 95 percent of the CPUs in the scheduling domain. That admission test is the capacity question rather than the ordering question, the same split as counting rooms versus assigning them. Media playback and robotics use it because a frame delivered late is as useless as one never delivered.
Why it works this way
Why sort by finish time, and not by start time or by shortest first?
Every other obvious key has a counterexample. Sorting by start time lets one interval that begins at 9 and runs all day knock out everything behind it; shortest first can pick a brief interval in the middle that straddles two longer ones which do not overlap each other, trading two for one. Earliest finish survives an exchange argument: take any optimal set, swap its first interval for the one that finishes earliest, and the set is still valid and still the same size. Repeat that swap and any optimum turns into the greedy answer, so the greedy answer was already optimal.
Ends sort before starts only because the intervals are half-open
Putting the end event first treats an interval as [start, end), so a meeting that ends at 10 does not conflict with one that starts at 10 and the room is reused. If your endpoints are inclusive on both sides, such as a booking held on days 3 to 5 against one on days 5 to 7, that really is a conflict and the tie has to sort starts first instead. The same assumption is baked into select: start >= lastEnd is the half-open test, and closed intervals need start > lastEnd. Getting the tie backwards only goes wrong on inputs whose endpoints touch, so it slips through casual testing, and it is not always off by one: four closed meetings, two running 1 to 5 and two running 5 to 9, all overlap at time 5, but ends-before-starts reports a peak of 2 instead of 4.
Why the peak overlap is exactly the room count, not just a lower bound
One half is easy: at the busiest instant k meetings are all in progress and no two of them can share a room, so k rooms are necessary. The other half is what partition proves: a meeting only opens a brand new room when every existing room is still busy at its start, which means all of those meetings plus this one overlap at that moment, so the room count can never exceed the peak. Most greedy algorithms only give you one of those halves and you settle for an approximation. Here the bound and the algorithm meet, so the sweep's peak is the exact answer.
Why job sequencing walks backwards from the deadline
Each job takes the latest free slot at or before its deadline, never the earliest. Filling from the front would burn slot 0 on a job due at time 5 and leave nothing for a job due at time 1; filling from the back keeps the tight early slots free for jobs that have nowhere else to go. The cost is that the backward walk is a linear scan, so a long run of taken slots makes the whole thing O(n * maxDeadline) in the worst case. Pointing each slot at the next free slot below it with a disjoint-set brings that back to near linear.
Read more
- Interval schedulingWikipedia
- Activity selection problemWikipedia
- Sweep line algorithmWikipedia
- Range types and exclusion constraintsPostgreSQL
- Deadline task schedulingLinux kernel · docs.kernel.org