Every interval must now be scheduled, into as few rooms as possible. The greedy rule opens a new room only when no existing one is free. The proof is not a stays-ahead or an exchange argument: it is a lower bound — the largest number of intervals alive at any single instant — computed by a routine that shares nothing with the scheduler, together with the list of intervals that attains it.
Core ideas
Three ideas: why a lower bound is a different kind of argument, what makes the depth a bound on every schedule rather than on this one, and why the certificate is listed on the page instead of being taken on trust.
Stays-ahead and exchange both reason about greedy against an optimum. A lower bound does not mention greedy at all: it names a quantity d and proves that no solution can use fewer than d rooms, whatever produced it. Then it is enough to show greedy uses d. The two halves are completely independent, which is why the panel computes them with two routines that share no code and prints both.
Fix any instant t and look at the intervals alive there. They all contain t, so every two of them overlap, so no two can go in the same room, so any schedule needs at least that many rooms. Take the instant where this count is largest and you have the depth. Nothing in that sentence mentions an algorithm, which is exactly what makes it apply to all of them.
“The depth is 3” is a claim a reader has to trust. The panel instead prints the instant — t = 2 on the opening instance — and the intervals alive there, A, B and C, and separately confirms that those three pairwise overlap. A reader can check that by eye in a few seconds and does not have to believe anything about how the depth was computed.
The material
The problem, the rule, the bound, the certificate, and the one control on this panel that changes nothing on any shipped instance.
Given n intervals, assign every one of them to a room so that no room holds two overlapping intervals, using as few rooms as possible. Unlike interval scheduling, nothing may be discarded: the question is not which intervals to keep but how many rooms they need.
For an instant t, the intervals alive at t are those with s ≤ t < f. The depth of an instance is the largest number of intervals alive at any single instant. The panel reports the instant that attains it alongside the number.
The lab opens on ten lectures: A 0-3, B 1-4, C 2-5, D 4-7, E 5-8, F 6-9, G 8-11, H 9-12, I 10-13, J 12-15. Greedy by start time opens three rooms and fills them A D G J, B E H and C F I. Every room is checked: no room holds two intervals that overlap, and all ten intervals were placed exactly once.
The depth is 3, attained at t = 2, where A 0-3, B 1-4 and C 2-5 are all alive. Those three pairwise overlap, so no schedule of any kind can put two of them in one room, so no schedule uses fewer than three rooms. Greedy used three. The two numbers were computed by separate routines and they agree, which is optimality demonstrated rather than asserted.
Sorting the intervals by start time and assigning each to the lowest-numbered room whose last booking has already finished opens exactly d rooms, where d is the depth. Hence it is optimal on every instance.
Suppose the rule opens room number d + 1 while placing some interval x. It only opens a new room when every one of rooms 1 through d is busy, which means each of those rooms holds an interval that has not finished by s(x).
Every such interval started at or before s(x), because the rule processes intervals in increasing start order and each of them was placed earlier. So each of those d intervals satisfies s ≤ s(x) and f > s(x), and is alive at the instant s(x). Together with x itself that is d + 1 intervals alive at one instant.
So the depth is at least d + 1, contradicting the assumption that it is d. The rule therefore never opens more than d rooms, and since no schedule can use fewer, it uses exactly d.
□
That proof needs the start order and uses it twice. The panel offers a second order — by finish time — and the theorem says nothing about it. On all four shipped instances the finish order opens the same number of rooms as the start order: three, two, five and one. A reader who moved that control on the presets and concluded the order does not matter would have measured four inputs and generalised to all of them.
It does matter, and the instance is small. Type 0-1, 1-4, 2-5, 4-9, 5-8. The depth is 2, attained at t = 2. By start time greedy opens two rooms, A B D and C E. By finish time it opens three: A B E, C and D. The finish order places E 5-8 into the first room because B finished at 4, and then D 4-9 fits nowhere. Same intervals, same rule shape, one more room than the bound.
The earlier arguments on this course both compare greedy with an optimal solution: stays ahead of it, or can be reached from it by swaps. This one never mentions an optimal solution. It proves a fact about every schedule — at least d rooms — and separately a fact about this one — at most d rooms. Two inequalities from two arguments, meeting.
That shape recurs for the rest of this path. An approximation ratio is the same construction with the two sides not meeting: a bound on every solution on one side, a measured quantity on the other, and the gap between them as the guarantee. This is the page where the gap happens to be zero, and noticing that it is a special case rather than the normal case is most of what the page is for.
Three things, and each exists because the corresponding claim is otherwise unverifiable. roomsValid confirms that every room's intervals are pairwise disjoint and that every input interval appears in exactly one room — an assignment that quietly dropped an interval would use fewer rooms and look better. liveAt lists the intervals alive at the certifying instant rather than reporting their number. mutuallyOverlapping then confirms that those listed intervals really do pairwise overlap, which is the step that makes the bound a bound.
Measured on this page: on the ten lectures greedy by start opens 3 rooms, the depth is 3, the certifying instant is t = 2, and the three intervals there pairwise overlap; on the five-interval pile-up all five are alive at t = 4 and five rooms are used; on the disjoint instance the depth is 1. Proved on this page: the start-order rule uses exactly the depth on every instance. The finish order has no such theorem, and the five-interval instance above is why.
Interactive
Rooms used and rooms needed, computed by two routines that share nothing
Method
Four steps. The third is the one that turns a number into a proof.
Assign each interval, in increasing start order, to the lowest-numbered room whose last booking has finished; open a new room only when none has. Record how many rooms that took. This is the upper bound and it is about your schedule.
Do not read it off the rooms. Sweep the instants, count what is alive at each, take the largest. On the opening instance that is 3, at t = 2. This is the lower bound and it is about every schedule.
Name the instant and list the intervals alive there, then check that they pairwise overlap. Three intervals that pairwise overlap need three rooms in any schedule whatsoever, and that sentence is the proof. “The depth is 3” on its own is something a reader has to take on faith.
Equal means optimal on this instance, for a reason that is on the screen. If they ever differ under the start order, something is wrong with the run rather than with the theory — and if they differ under the finish order, nothing is wrong at all, because no theorem covers it.
Intervals in typed order: A 0-3, B 1-4, C 2-5, D 4-7, E 5-8, F 6-9, G 8-11, H 9-12, I 10-13, J 12-15. They are already in increasing start order, so the rule walks them as typed.
The instant t = 2 is doing all the work. A, B and C each contain it, so each pair of them overlaps, so a schedule that put any two in one room would be illegal. That argument mentions no algorithm and therefore constrains every algorithm, including ones nobody has written.
A third room was opened at C and never again, although seven more intervals arrived. That is the proof's mechanism in miniature: a new room is opened only when every existing one is busy, and every existing one being busy at s(x) means that many intervals are alive at s(x).
For a faded rehearsal, work out the rooms and the depth for 0-1, 1-4, 2-5, 4-9, 5-8 under both orders before running it. The supplied first move is this: by start time the walk is A 0-1, B 1-4, C 2-5, D 4-9, E 5-8, and A and B both land in room 1 because A finishes exactly when B starts. Say how many rooms each order opens, what the depth is, and which of the two orders the theorem actually covers.
You should be able to run the room assignment by hand, compute the depth independently, state the certificate as an object rather than a number, reproduce the proof that the start-order rule never opens more rooms than the depth, and explain why the same proof says nothing about the finish order.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.