☕ DSA Java Articles

Topics › Greedy Algorithms › Medium/Hard

Meeting Rooms II

Medium TUF ID 710 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of meeting times intervals, where intervals[i] = [start_i, end_i]. Return the minimum number of conference rooms needed so that every meeting can take place.

A meeting occupies the half-open range [start, end), so a room freed at time 10 can host a meeting that starts at 10. The input is in no particular order.

Constraints: 1 ≤ n ≤ 10^4, 0 ≤ start_i < end_i ≤ 10^6. (LeetCode 253, a premium problem; LintCode 919 is the same with an Interval class.) The code also accepts an empty array and returns 0.

Example 1

intervals = [[0, 30], [5, 10], [15, 20]]
answer = 2          // [0, 30) overlaps both others, but [5, 10) and [15, 20) can share a room

Example 2

intervals = [[7, 10], [2, 4]]
answer = 1          // the meetings never run at the same time

Reframing the question

The number of rooms needed is exactly the largest number of meetings running at the same moment. It cannot be smaller: at that moment each running meeting needs its own room. And it is enough, as the min-heap approach below proves by actually building such a schedule. So the task becomes “find the maximum overlap of n half-open intervals”, the same question as the railway platform problem.

Approach 1: Brute force, count the meetings running at every start time

Intuition. The number of running meetings only goes up when a meeting starts; ends only bring it down. So the maximum is reached at some meeting’s start time. Take the busiest moment and slide back to the latest start among the meetings running then: all of them have started by that point and none has ended. It is therefore enough to count, for each start time t, the meetings with start ≤ t < end.

Algorithm.

  1. For each meeting, let t be its start.
  2. Count the meetings other with other.start ≤ t < other.end.
  3. Return the largest count.
static int bruteForce(int[][] intervals) {
    int best = 0;
    for (int[] m : intervals) {
        int t = m[0], running = 0;
        for (int[] other : intervals) {
            if (other[0] <= t && t < other[1]) running++;   // other is in progress at time t
        }
        best = Math.max(best, running);
    }
    return best;
}

Complexity. Time O(n^2): n candidate moments, n meetings checked at each. Space O(1).

Approach 2: Sort by start and keep a min-heap of end times

Intuition. Act like a receptionist handing out rooms as meetings start, in start order. Keep one heap entry per room in use, holding the time that room becomes free. The heap’s top is the room that frees up first. When a meeting starts at s:

Either way the new meeting’s end time goes into the heap. The heap never shrinks (each step removes at most one entry and always adds one), so its final size is the number of rooms ever opened.

Why this is the minimum: look at the moment a new room is opened at time s. Every meeting in the heap started at or before s (we process meetings in start order) and ends after s (even the smallest end in the heap is > s). So all of them, plus the new meeting, run at time s, and any schedule needs at least that many rooms. The greedy schedule never uses more rooms than some moment forces.

Algorithm.

  1. Copy and sort the meetings by start time.
  2. For each meeting [s, e]: if the heap is not empty and heap.peek() ≤ s, poll it. Then push e.
  3. Return the heap’s size.
static int minHeap(int[][] intervals) {
    int[][] a = intervals.clone();
    Arrays.sort(a, (x, y) -> Integer.compare(x[0], y[0]));
    PriorityQueue<Integer> ends = new PriorityQueue<>();      // end time of the meeting in each occupied room
    for (int[] m : a) {
        if (!ends.isEmpty() && ends.peek() <= m[0]) ends.poll(); // the room that frees up first is free: reuse it
        ends.add(m[1]);
    }
    return ends.size();                                        // the heap never shrinks, so this is its peak size
}

Dry run on Example 1, sorted as [0, 30], [5, 10], [15, 20]:

meeting heap before top ≤ start? heap after
[0, 30] {} empty {30}
[5, 10] {30} 30 ≤ 5, no: new room {10, 30}
[15, 20] {10, 30} 10 ≤ 15, yes: reuse {20, 30}

The heap ends with 2 entries, so 2 rooms.

Complexity. Time O(n log n): the sort plus n heap operations of O(log n) each. Space O(n) for the sorted copy and the heap.

Approach 3: Chronological sweep with two sorted arrays

Intuition. The heap remembers which meeting is in which room, but the count only depends on when things start and end. Turn every meeting into two events, +1 at its start and -1 at its end, and walk through all events in time order while tracking the number of rooms in use. Sorting the starts and the ends separately and merging them with two pointers gives that order without building event objects.

Ties matter. When a meeting ends at 10 and another starts at 10, the end must be processed first because the room is reusable at 10. That is why the inner loop releases every end ≤ starts[i] before counting the start. The pointer j cannot run past the array: each released end belongs to a meeting that started strictly earlier, so at most i ends are released before start i.

Algorithm.

  1. Copy all start times into starts and all end times into ends; sort both.
  2. For each start in order: while ends[j] ≤ starts[i], decrement inUse and advance j. Then increment inUse and update best.
  3. Return best.
static int sweep(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 inUse = 0, best = 0, j = 0;
    for (int i = 0; i < n; i++) {
        while (ends[j] <= starts[i]) {   // meetings that ended by now give their rooms back (ends win ties)
            inUse--;
            j++;
        }
        inUse++;                         // the meeting starting at starts[i] takes a room
        best = Math.max(best, inUse);
    }
    return best;
}

Dry run on Example 1: starts = [0, 5, 15], ends = [10, 20, 30].

i starts[i] ends released inUse best
0 0 none 1 1
1 5 none (10 > 5) 2 2
2 15 10 2 2

Complexity. Time O(n log n) for the two sorts; the sweep is O(n). Space O(n) for the two arrays. If times are small integers (here at most 10^6), a difference array of size maxTime + 1 with +1 at each start and -1 at each end, followed by a prefix sum, removes the sort and gives O(n + maxTime). A TreeMap<Integer, Integer> of the same +1/-1 deltas works for arbitrary times.

Edge cases and pitfalls