Interval Partitioning

Schedule all intervals using the fewest resources (rooms, machines, platforms), where each resource handles one interval at a time.

The answer

The minimum number of rooms equals the maximum number of intervals overlapping at any single point (the “depth”).

Lower bound: at a moment when $d$ intervals are simultaneously active, $d$ rooms are clearly necessary. Upper bound: the greedy below never uses more than $d$.

The sweep — $O(n\log n)$

int minRooms(vector<pair<int,int>>& iv) {
    vector<pair<int,int>> ev;
    for (auto& [s, e] : iv) { ev.push_back({s, +1}); ev.push_back({e, -1}); }
    sort(ev.begin(), ev.end());              // at equal times, -1 sorts before +1
    int cur = 0, best = 0;
    for (auto& [t, d] : ev) { cur += d; best = max(best, cur); }
    return best;
}

The tie-break at equal times encodes whether an interval ending at $t$ frees the room for one starting at $t$ — the half-open convention. Since -1 < +1, the sort above releases first, which is usually what is meant.

Assigning actual rooms

vector<int> assignRooms(vector<array<int,3>>& iv) {        // {start, end, id}
    sort(iv.begin(), iv.end());                            // by start
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // (endTime, room)
    vector<int> room(iv.size());
    int rooms = 0;
    for (auto& [s, e, id] : iv) {
        if (!pq.empty() && pq.top().first <= s) {
            room[id] = pq.top().second; pq.pop();           // reuse a free room
        } else {
            room[id] = rooms++;                             // open a new one
        }
        pq.push({e, room[id]});
    }
    return room;
}

$O(n\log n)$, and the number of rooms opened is provably the maximum depth.

Colouring interpretation

Build the interval graph: a vertex per interval, an edge between overlapping ones. Then:

• minimum rooms = chromatic number of that graph;
• maximum simultaneous overlap = size of the maximum clique.

Interval graphs are perfect, so $\chi =\omega$ — which is exactly the theorem above. In a general graph, colouring is NP-hard; the interval structure is what makes greedy optimal here.

This also means, on interval graphs:

• maximum independent set = max non-overlapping intervals (greedy),
• maximum clique = maximum depth (sweep),
• minimum clique cover = max independent set,

all polynomial, all by sorting.

Variants

Problem	Method
Minimum rooms	maximum depth (sweep)
Assign specific rooms	greedy + a min-heap
Rooms with capacities	flow, or a greedy with a heap keyed by capacity
Minimum rooms with setup time $g$ between bookings	extend each interval’s end by $g$
Maximum intervals with only $k$ rooms	greedy + a size-$k$ heap, or min-cost flow
Depth at every point	difference array
Minimum rooms on a circle (cyclic time)	try each cut point, or use the circular depth
Intervals arrive online	greedy is $O(\log n)$-competitive; no online algorithm is optimal

Related classics

Minimum platforms. Trains arrive and depart; the minimum number of platforms is the maximum simultaneous occupancy — the identical problem.

Meeting rooms II. The same, phrased as meetings.

Maximum concurrent events. The same sweep.

CPU scheduling with $k$ cores. With fixed start and end times, the same; with flexible start times it becomes a makespan problem, which is NP-hard.

The general lesson

“Minimise the number of resources” and “maximise the simultaneous demand” are dual, and on intervals they are equal. That duality is what makes a sweep sufficient. When the structure is not an interval graph, the equality breaks and the problem usually becomes NP-hard — so identifying that intervals are involved is the whole insight.

See also: Interval Scheduling · Sweep Line · Difference Array