Meeting Rooms II (LC 253)

Pattern: Min-Heap of End Times (or Sweep-Line) Difficulty: Medium Key Concept: At any moment, the number of rooms in use equals the number of meetings whose start ≤ now < end. Process meetings by start time; reuse a room whenever the earliest end time is already ≤ this start.

Problem Statement

Given an array intervals of meeting times [start, end], return the minimum number of conference rooms required so that no two meetings overlap.

Example

• intervals = [[0,30],[5,10],[15,20]] → 2
• intervals = [[7,10],[2,4]] → 1

---

1. Algorithm & Pseudocode

Heap approach

sort intervals by start
heap = min-heap of currently-occupied rooms' end times
for each meeting (s, e):
    if heap not empty and heap.peek() <= s:
        heap.poll()         // room freed before this meeting starts
    heap.offer(e)
return heap.size()

Sweep-line approach

collect all start times into starts[], sort
collect all end times   into ends[],   sort

i = 0, rooms = 0, max = 0
for s in starts:
    if s < ends[i]:
        rooms++             // need a new room
    else:
        i++                 // one meeting freed a room
    max = Math.max(max, rooms)
return max

---

2. Step-by-Step Analysis

Why sort by start Meetings must be considered in the order they begin. Otherwise we might “free” a room for a meeting that hasn’t started yet.

Why a min-heap of end times The room that becomes available earliest is the one whose end time is smallest. A min-heap gives us that in O(log n) per operation.

Why we check peek() <= s (not <) Convention: a meeting ending at time 10 frees its room at 10, so a meeting starting at 10 can reuse it. (LeetCode uses this convention; some variations require strict <.)

Why heap size is the answer Heap size at any moment = number of meetings currently active. We add each meeting and only remove when reusing — so the final size equals the max concurrent load.

ASCII Trace for [[0,30],[5,10],[15,20]]

sorted by start: [0,30] [5,10] [15,20]

meeting [0,30]:  heap empty → offer 30      heap = [30]
meeting [5,10]:  peek 30 > 5 → offer 10     heap = [10, 30]
meeting [15,20]: peek 10 ≤ 15 → poll, offer 20  heap = [20, 30]

max size reached = 2

---

3. The Dry Run

intervals = [[0,30],[5,10],[15,20]]

Step	Meeting	heap.peek()	Action	Heap (after)
1	(0,30)	—	offer 30	[30]
2	(5,10)	30 > 5	offer 10	[10, 30]
3	(15,20)	10 ≤ 15	poll, offer 20	[20, 30]

Return heap.size() = 2.

---

4. Java Solution

Heap

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int[] m : intervals) {
            if (!heap.isEmpty() && heap.peek() <= m[0]) heap.poll();
            heap.offer(m[1]);
        }
        return heap.size();
    }
}

Time: (O(n \log n)) Space: (O(n))

Sweep-line

class Solution {
    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, max = 0, i = 0;
        for (int s : starts) {
            if (s < ends[i]) rooms++;
            else { i++; }                 // a meeting ended, freeing a room — no net change
            max = Math.max(max, rooms);
        }
        return max;
    }
}

Time: (O(n \log n)) Space: (O(n))

---

5. The “Java vs. Others” Edge

• PriorityQueue<Integer> is a min-heap by default — no comparator needed.
• For huge inputs, the sweep-line version has lower constant factor (only primitives, no heap restructuring).
• Watch the comparator: (a,b) -> a[0] - b[0] can overflow if values can be Integer.MIN_VALUE. Use Integer.compare(a[0], b[0]) to be safe.

---

6. Complexity Summary

Approach	Time	Space	Notes
Min-Heap	(O(n \log n))	(O(n))	Clean, mirrors the mental model.
Sweep-Line	(O(n \log n))	(O(n))	Lowest constants in practice.