Meeting Rooms II

1. Problem & Core Objective

Given an array of meeting time intervals, return the minimum number of conference rooms required.

[[0,30],[5,10],[15,20]]      →  2
[[7,10],[2,4]]               →  1
[[0,3],[1,5],[4,6],[6,8]]    →  2

Constraints: 1 <= intervals.length <= 10^4, start_i < end_i, values up to 10^6.

What's actually being tested: recognising that the answer is a property of the timeline, not of the meetings. The minimum number of rooms equals the maximum number of meetings running at any single instant — and once you believe that, three different algorithms fall out of it.

2. First-Principles Thought Process

The answer is the peak concurrency

Two directions:

• Lower bound. If k meetings are simultaneously in progress at some instant, they need k distinct rooms at that instant. So the answer is at least the peak.
• Upper bound. peak rooms always suffice. Process meetings in order of start time and assign each to any free room. A room is unavailable only if its meeting is still running, so if fewer than peak rooms were free you'd have peak or more meetings concurrently in progress — a contradiction with peak being the maximum.

So the answer equals the peak, exactly. That's a proof, not an intuition, and it converts a resource-allocation question into a counting question.

The decoupling insight

Once you're counting concurrency, the pairing between a start and its own end stops mattering. What matters is only the multiset of events: +1 at every start, −1 at every end. Sort them, sweep, track the running total, take the maximum.

That's why you're allowed to sort the starts and the ends into two separate arrays and lose track of which belonged to which. It looks like vandalism and it's exactly right — the timeline doesn't care which meeting occupies a room, only how many are occupied.

Half-open, again

A meeting ending at 5 frees its room for one starting at 5. So at time 5 the end is processed before the start:

while (j < n && ends[j] <= starts[i]) { rooms--; j++; }     // <=, not <

In the heap formulation the same decision is ends.peek() <= m[0]. Using < would keep the room occupied through the handover and inflate the answer on back-to-back meetings.

Note this is the opposite tie-break from Merge Intervals's sweep-line variant, where starts must be processed first so that touching intervals merge. Same machinery, opposite convention, because the questions differ: merging asks whether the union is connected, scheduling asks whether both can happen.

Why the heap tracks exactly the right thing

Sort by start and keep a min-heap of the end times of currently-occupied rooms. For each new meeting:

1. If the earliest end is <= this meeting's start, that room is free — pop it.
2. Push this meeting's end.

The heap size is then the number of rooms in use, and its maximum over the sweep is the answer. Only one pop is needed per meeting, not a loop: popping two would mean the heap size drops, and since it only grows by one per meeting, freeing more than one room can never be necessary to accommodate a single new meeting.

Measured: never popping at all — never freeing a room — gives the wrong answer on 2,759 of 4,000 random inputs. It degenerates to returning n.

3. Solution Paths

Approach 1 — Brute force: count concurrency at every start

public int minMeetingRooms(int[][] intervals) {
    int best = 0;
    for (int[] p : intervals) {
        int t = p[0], concurrent = 0;
        for (int[] q : intervals)
            if (q[0] <= t && t < q[1]) concurrent++;     // q is running at time t
        best = Math.max(best, concurrent);
    }
    return best;
}

• Time O(n²) · Space O(1)

The reference the optimal versions were checked against, on 4,000 random inputs.

Counter-questions on this approach

⭐ "Why is it enough to sample only at meeting start times?"

Because concurrency only ever increases at a start. Between consecutive events it's constant, and ends only decrease it — so the maximum is attained immediately after some start.

That means the n start times are a sufficient sample of the continuous timeline. Sampling every integer instant would be correct but O(range × n), and wrong for non-integer times.

"Why q[0] <= t && t < q[1] rather than <= on both?"

Half-open. A meeting occupies its room on [start, end), so it is running at t iff t is at or after its start and strictly before its end. Using t <= q[1] would count a meeting that has just ended.

Every formulation of this problem has exactly one place where that decision lives. Here it's this line.

"Would you ever ship this?"

At n = 10^4 it's 10^8 comparisons — a second or so, probably too slow. Its job is to be obviously correct for differential testing, which it was: it caught nothing, which is the point of having it.

Approach 2 — Sweep separated start and end arrays (optimal)

public int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] starts = new int[n], ends = new int[n];
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0, best = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (j < n && ends[j] <= starts[i]) { rooms--; j++; }   // free every room that has ended
        rooms++;
        best = Math.max(best, rooms);
    }
    return best;
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "You've thrown away which end belongs to which start. Justify that."

The question is about counts over time, and counts don't depend on the pairing. At the moment starts[i] occurs, the number of meetings that have begun is i+1 and the number that have finished is however many ends are <= starts[i] — which is j. The difference is the concurrency, regardless of who paired with whom.

Concretely: swapping the ends of two overlapping meetings changes which room each occupies but not how many rooms are needed at any instant.

⭐ "Why is the inner while loop not quadratic?"

j only ever increases and never exceeds n across the entire outer loop. So the total work in the inner loop is O(n) over all iterations — the standard two-pointer amortisation.

The nesting is syntactic, not algorithmic.

"Why <= in the while condition?"

A meeting ending exactly when another starts frees its room in time. With <, back-to-back meetings would each hold a room and the answer would be inflated — which is most pairs on a realistic calendar.

"Could rooms be computed as i + 1 - j instead of incremented?"

Yes, and it's arguably clearer: i+1 meetings have started and j have ended. I kept the increment/decrement form because it mirrors the +1/−1 event framing that generalises to weighted sweeps.

Both are correct; worth having the alternative ready since it removes a mutable variable.

"Does this need the meetings themselves after the extraction?"

No — which is a nice property. Once the two sorted arrays exist the original input is irrelevant, so this streams naturally if the starts and ends arrive from separate sources.

Approach 3 — Min-heap of end times

public int minMeetingRooms(int[][] intervals) {
    if (intervals.length == 0) return 0;
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

    PriorityQueue<Integer> ends = new PriorityQueue<>();      // end times of occupied rooms
    for (int[] m : intervals) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll();   // the earliest room is free
        ends.add(m[1]);
    }
    return ends.size();
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "Why does the final heap size equal the maximum concurrency rather than the final concurrency?"

Because the heap never shrinks. Each meeting pops at most one entry and always pushes one, so the size is non-decreasing — it records the high-water mark rather than the current occupancy.

That's initially counter-intuitive: the heap holds stale end times for rooms that were freed and reused. But a "room" here is an identity that persists, and the count of identities ever needed is the answer.

⭐ "Why pop at most once per meeting rather than draining every expired end?"

Because one new meeting can occupy only one room. Draining more would shrink the heap below the high-water mark and lose the maximum.

If you did want to drain — for a version that reports current occupancy over time — you'd have to track the maximum separately. The single-pop version encodes the answer in the size, which is why it's so short.

⭐ "What if you never pop at all?"

The heap grows to n and the answer becomes the number of meetings. Measured: wrong on 2,759 of 4,000 random inputs — it's right only when no two meetings can share a room at all.

"Why a min-heap rather than a max-heap?"

The relevant room is the one freeing soonest, because that's the only one that could possibly accommodate a meeting starting now. A max-heap would surface the room busy the longest, which is never the one you want.

PriorityQueue<Integer> is a min-heap by default in Java (14).

"Why must the meetings be sorted by start first?"

Because the algorithm decides a room is free by comparing against the current meeting's start, which only makes sense if meetings are processed in chronological order. Out of order, a later-starting meeting could free a room for an earlier one that hasn't been seen yet.

"Heap or two-pointer sweep — which would you write?"

The heap, because it generalises: swap PriorityQueue<Integer> for PriorityQueue<Room> and it assigns actual room identifiers, which is the natural follow-up. The sweep is faster in practice — two primitive sorts and no boxing — but it only ever produces a count.

Approach 4 — Difference array / coordinate compression

public int minMeetingRooms(int[][] intervals) {
    TreeMap<Integer,Integer> delta = new TreeMap<>();
    for (int[] m : intervals) {
        delta.merge(m[0],  1, Integer::sum);
        delta.merge(m[1], -1, Integer::sum);
    }
    int rooms = 0, best = 0;
    for (int d : delta.values()) { rooms += d; best = Math.max(best, rooms); }
    return best;
}

• Time O(n log n) · Space O(n)

Counter-questions on this approach

⭐ "Why does TreeMap handle the half-open convention automatically?"

Because a start and an end at the same time land in the same key and their +1 and −1 cancel before the running total is read. The room is freed and re-occupied atomically, so concurrency never spuriously spikes.

That's a real advantage over an explicit event list, where the ordering of equal-time events has to be specified by hand — and getting that tie-break backwards is the classic sweep-line bug.

"When is this the best choice?"

When times are small integers — then it's an int[] difference array and O(range + n) with tiny constants. And when the follow-up asks for concurrency over time rather than just the peak, since the map already holds the full profile.

"What's the downside?"

Boxing and tree traversal make it slower than two primitive sorts, and it allocates a node per distinct time. For a pure "give me the peak" answer the sweep is better.

4. Why the Optimal Solution Wins

O(n log n) is optimal in the comparison model — this subsumes element distinctness.

Write the heap version unless asked for raw speed. It states the mechanism — "these are the rooms currently busy, and the smallest end is the next to free" — in a way the two-pointer sweep doesn't, and the follow-up ("which room does each meeting get?") is a one-line change.

5. Java Prerequisites

PriorityQueue is a min-heap

PriorityQueue<Integer> pq = new PriorityQueue<>();                       // min-heap
PriorityQueue<Integer> mx = new PriorityQueue<>(Comparator.reverseOrder());  // max-heap
pq.peek();   // smallest, O(1), null if empty
pq.poll();   // remove smallest, O(log n)
pq.add(x);   // O(log n)

peek returns null rather than throwing, so !pq.isEmpty() && pq.peek() <= x is the safe order — the short-circuit prevents unboxing a null (14).

Two-pointer amortisation

for (int i = 0; i < n; i++) {
    while (j < n && cond) j++;      // j never resets — O(n) total, not O(n²)
    ...
}

TreeMap.merge for a difference map

delta.merge(key, 1, Integer::sum);      // insert 1, or add 1 to the existing value

Entries with a net delta of 0 remain in the map with value 0, which is harmless for a running sum.

Primitive versus object sorts

Arrays.sort(starts);                                             // int[]: dual-pivot quicksort, no boxing
Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));      // int[][]: TimSort, comparator call per compare

The first is meaningfully faster — which is the whole practical argument for Approach 2.

6. Interview Communication Guide

Clarifying questions: Does a meeting ending at 5 free the room for one starting at 5 (yes — half-open, and it changes the answer on back-to-back pairs)? Do I return the count or the actual assignment (count — I'll note how to get the assignment)? Are meeting times integers (if they're small integers, a difference array is an option)? Can the list be empty (answer 0)?

The pitch

"The key claim is that the minimum number of rooms equals the maximum number of meetings running at any one instant.

Both directions are easy. If k meetings overlap at some moment they need k rooms, so the answer is at least the peak. And the peak always suffices: process meetings in start order and assign each to any free room — if fewer than peak rooms were free, that many meetings would be concurrently in progress, contradicting the peak.

So it's a counting problem on the timeline, and the pairing between a start and its own end stops mattering. That licenses the neat solution: pull the starts into one sorted array and the ends into another, then walk them with two pointers. At each start, free every room whose end has already passed, then occupy one, and track the running maximum. The inner loop is amortised O(n) because the end pointer never resets.

Alternatively a min-heap of the end times of occupied rooms, which I slightly prefer because it names what's happening — the smallest end is the next room to free. Pop at most once per meeting, since one meeting can only take one room, and the heap's final size is the answer because it never shrinks.

The convention point: ends[j] <= starts[i], with <=, because a meeting ending at 5 frees its room for one starting at 5. Using < inflates the answer on every back-to-back pair. Note that's the opposite tie-break from a merge-intervals sweep, where starts must go first so touching intervals merge.

O(n log n) for the sorts, O(n) space. If times were small integers I'd use a difference array over the timeline instead — O(range + n), and it also gives the concurrency profile rather than just the peak."

Edge cases to volunteer:

Name [[1,10],[2,3],[4,5],[6,7]]. It's the input that separates "count the meetings that overlap something" from "count the peak" — three meetings overlap [1,10], but the answer is 2, because they never overlap each other.

7. Follow-Up Questions — Modified Constraints

⭐ "Assign each meeting an actual room number."

Replace the min-heap of end times with a min-heap of (endTime, roomId). Popping a free room reuses its id; if none is free, mint a new one. The final count of minted ids is the answer, and every meeting carries its room.

Same O(n log n). This is the reason to prefer the heap formulation — the two-pointer sweep has deliberately destroyed the information you'd need.

⭐ "Report the concurrency at every point in time, not just the peak."

The difference-map version already computes it: the running prefix sum over the TreeMap is the profile. O(n log n) to build, O(distinct times) to report.

The heap and sweep versions would need extra bookkeeping, because they only ever look at the maximum.

"What if each meeting also required a specific room feature — projector, capacity?"

No longer a sweep. It becomes bipartite matching between meetings and rooms with compatibility constraints, solved by max-flow or Hopcroft–Karp. The clean concurrency argument collapses the moment rooms stop being interchangeable.

Worth naming explicitly, because the entire proof in §2 rests on rooms being identical.

"What if you were given k rooms and had to maximise the number of meetings held?"

That's k-track interval scheduling — sort by end and greedily assign to any room free by that meeting's start, tracking room ends in a min-heap. O(n log k).

Note the sort key flips to end, because now you're choosing which meetings to keep (Non-Overlapping Intervals) rather than accommodating all of them.

"What if meetings could be moved by up to 15 minutes?"

Scheduling with slack — no longer solvable by a sweep, since the events aren't fixed. It becomes a constraint problem, and the general version is NP-hard. A useful partial answer: the peak concurrency is still a lower bound, so it bounds how much slack could possibly help.

"What if meetings recurred daily and you wanted rooms for a steady state?"

Times become circular. Any meeting crossing midnight is split into two, and the concurrency at midnight has to account for the wrap. After splitting, the ordinary sweep applies — the same wrap-handling trick as in Meeting Rooms.

"What if n were 10^8 but times were minutes in a day?"

Difference array over 1,440 buckets. O(n + 1440), no sorting, O(1) space beyond the fixed array. When the coordinate range is tiny relative to n, counting beats sorting — and this is the cleanest example of it in the section.