interval partitioning

Now flip the interval problem around. Instead of one room and as many lectures as fit, you must schedule ALL the lectures, each in some room, with no two overlapping lectures sharing a room — and you want to use as FEW rooms as possible. Think of classes that all must happen; how many classrooms does the timetable need at minimum?

There is a beautiful lower bound first: at any single instant, count how many intervals are live (in progress) at that moment; the largest such count is called the depth. You obviously need at least 'depth' rooms, because that many lectures genuinely overlap at one point and each needs its own room. The greedy algorithm matches this bound. Sort intervals by start time; sweep through them; for each interval, assign it to any room that is currently free (its last lecture has already finished); if none is free, open a new room. The proof that this uses exactly 'depth' rooms: a new room is opened only when an interval starts and every existing room is busy, meaning all those rooms plus the new one are live simultaneously — so when you open room number k, there are k overlapping intervals, hence depth is at least k. Greedy never opens more rooms than the depth forces, and never fewer than required, so it is optimal. With a min-heap keyed on room free-times this runs in O(n log n).

Interval partitioning is the same thing as coloring an interval graph with the fewest colors, and it is a clean case where greedy hits a provable lower bound exactly. The point worth remembering: depth (maximum simultaneous overlap) is the answer, and the greedy sweep is just an efficient, constructive way to achieve it. A common mistake is sorting by finish time here as in the single-room problem — for partitioning you must sort by START time so you process intervals in the order they begin.