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.
5 jobs, each taking one time slot and each with a deadline and a profit: a by 2 for 100, b by 1 for 19, c by 2 for 27, d by 1 for 25, e by 3 for 15. Take the jobs richest first, and give each the latest free slot before its deadline, so earlier slots stay open for jobs with tighter deadlines. A job with no free slot left is dropped.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 5, with their answers.
Job a pays 100 and must finish by slot 2. Where does it go?
Answer: Slot 2. The latest free slot at or before the deadline, or nowhere if all of them are taken.
Job c pays 27 and must finish by slot 2. Where does it go?
Answer: Slot 1. The latest free slot at or before the deadline, or nowhere if all of them are taken.
Job d pays 25 and must finish by slot 1. Where does it go?
Answer: Slot 1. The latest free slot at or before the deadline, or nowhere if all of them are taken.
Job b pays 19 and must finish by slot 1. Where does it go?
Answer: Slot 1. The latest free slot at or before the deadline, or nowhere if all of them are taken.
Job e pays 15 and must finish by slot 3. Where does it go?
Answer: Slot 3. The latest free slot at or before the deadline, or nowhere if all of them are taken.
How it runs, step by step
5 jobs, each taking one time slot and each with a deadline and a profit: a by 2 for 100, b by 1 for 19, c by 2 for 27, d by 1 for 25, e by 3 for 15. Take the jobs richest first, and give each the latest free slot before its deadline, so earlier slots stay open for jobs with tighter deadlines. A job with no free slot left is dropped.
Job sequencing with 5 jobs over 3 slots.
Job a, profit 100, deadline 2: slot 2 is free, so it goes there. Total profit 100.
Job a in slot 2.
Job c, profit 27, deadline 2: slot 2 is taken, so it walks back to slot 1. Total profit 127.
Job c in slot 1.
Job d, profit 25, deadline 1: every slot from 1 to 1 is taken by a richer job, so it is skipped.
Job d skipped.
Job b, profit 19, deadline 1: every slot from 1 to 1 is taken by a richer job, so it is skipped.
Job b skipped.
Job e, profit 15, deadline 3: slot 3 is free, so it goes there. Total profit 142.
Job e in slot 3.
Schedule 1: c, 2: a, 3: e, total profit 142 with 3 placed and 2 skipped. Taking the richest job first and the latest possible slot is optimal: an exchange argument shows any schedule that leaves out a richer job for a poorer one can be improved. O(n log n) to sort, O(n x slots) to place naively.
Total profit 142.
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