Meeting Rooms II (LC 253)

Pattern: Merge Intervals / Sweep Line
Difficulty: Medium
Key Concept: The minimum number of conference rooms equals the maximum number of meetings happening at the same time; track “active” meetings via a min-heap of end times or a two-pointer sweep over starts and ends.

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that no two meetings in the same room overlap.

Input: int[][] intervals.
Output: int — minimum rooms.

1. Algorithm & Pseudocode

Brute force (simulation idea)

At each distinct time (or for each meeting start), count how many meetings are in progress (start ≤ t < end).
Answer is the maximum of those counts.
(Implementations often discretize times or check all pairs of intervals—expensive.)

Optimal 1 — Sort + min-heap (PriorityQueue)

Sort meetings by start time.
Use a min-heap of end times of meetings currently using a room (earliest finishing meeting on top).
For each meeting [s, e]:
- If heap not empty and peek() ≤ s, poll() (that room frees up) and offer(e).
- Else offer(e) (need another room).
Answer = max heap size during the process, or heap size at end after processing all (track max while iterating).

Optimal 2 — Chronological ordering (two pointers)

Build arrays starts[] and ends[] from all intervals; sort both.
i = 0, j = 0, active = 0, maxRooms = 0.
While i < n:
- If starts[i] < ends[j]: active++, maxRooms = max(maxRooms, active), i++.
- Else: active--, j++.
Return maxRooms.

2. Step-by-Step Analysis (Beginner-Friendly)

Why heap of end times? The earliest-ending active meeting is the one that might free a room first. If the next meeting starts at or after that end, we reuse one room (pop old end, push new end).
Why peek() <= start means reuse? Room is free from peek onward; a meeting starting at start can use it if start ≥ that end. Using <= matches “end at 10, start at 10” as non-overlapping (back-to-back).
Two-pointer intuition: Imagine sweeping a timeline: each start increases concurrent count; each end decreases it. Sorting starts and ends separately lets us process events in order without a heap.
Interview tip: Many interviewers accept either approach; heap is very common; chronological shows you understand sweep line thinking.

3. The Dry Run

Input: intervals = [[0,30],[5,10],[15,20]]
Sorted by start: [[0,30],[5,10],[15,20]].

Heap approach

Step	Meeting	Heap (min-heap of ends) before	Action	Heap after	`maxSize`
1	`[0,30]`	`[]`	push `30`	`[30]`	1
2	`[5,10]`	`[30]`	`peek 30 > 5` → cannot reuse; push `10`	`[10,30]`	2
3	`[15,20]`	`[10,30]`	`peek 10 <= 15` → poll `10`, push `20`	`[20,30]`	2

Answer: 2 rooms.

Two-pointer approach

starts = [0, 5, 15], ends = [10, 20, 30] (sorted).

Step	`starts[i]`	`ends[j]`	Comparison	`active`	`maxRooms`	Move
Init	—	—	—	0	0	—
1	0	10	`0 < 10`	1	1	`i++`
2	5	10	`5 < 10`	2	2	`i++`
3	15	10	`15 < 10` false	1	2	`j++`
4	15	20	`15 < 20`	2	2	`i++`
5	—	—	`i == n`, stop	—	2	—

Answer: 2 rooms.

4. Java Solution

Brute Force

import java.util.*;

class Solution {
    // Conceptual O(n^2) or worse depending on time discretization — pair-based overlap count
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        int n = intervals.length;
        int maxOverlap = 0;
        for (int i = 0; i < n; i++) {
            int s1 = intervals[i][0], e1 = intervals[i][1];
            int count = 0;
            for (int j = 0; j < n; j++) {
                int s2 = intervals[j][0], e2 = intervals[j][1];
                if (s2 < e1 && s1 < e2) {
                    count++;
                }
            }
            maxOverlap = Math.max(maxOverlap, count);
        }
        return maxOverlap;
    }
}

Time: O(n²). Space: O(1).
(Note: This counts, for each anchor interval, how many intervals overlap it; the global maximum concurrent meetings equals the answer for interval graphs on a line.)

Optimal 1 — Min-heap

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int maxRooms = 0;
        for (int[] m : intervals) {
            int start = m[0], end = m[1];
            while (!pq.isEmpty() && pq.peek() <= start) {
                pq.poll();
            }
            pq.offer(end);
            maxRooms = Math.max(maxRooms, pq.size());
        }
        return maxRooms;
    }
}

Time: O(n log n). Space: O(n) for the heap.

Optimal 2 — Two pointers

import java.util.Arrays;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        int n = intervals.length;
        int[] starts = new int[n];
        int[] 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 i = 0, j = 0;
        int active = 0;
        int maxRooms = 0;
        while (i < n) {
            if (starts[i] < ends[j]) {
                active++;
                maxRooms = Math.max(maxRooms, active);
                i++;
            } else {
                active--;
                j++;
            }
        }
        return maxRooms;
    }
}

Time: O(n log n). Space: O(n) for the copied arrays.

5. The “Java vs. Others” Edge

PriorityQueue defaults to min-heap (smallest peek()). For end times, that is exactly “next room to free.”
Custom comparator: new PriorityQueue<>((a, b) -> a - b) works for Integer; for primitive int stored as Integer, natural order is fine: new PriorityQueue<>().
peek() vs poll(): Always check non-empty before peek/poll when logic requires; the loop while (!pq.isEmpty() && pq.peek() <= start) poll() frees all rooms that have ended before start (usually one suffices per step, but multiple identical ends is handled).
C++: priority_queue<int, vector<int>, greater<int>> gives a min-heap; Java’s PriorityQueue is min by default—easy contrast for interviews.
Python: heapq is min-heap; same pattern as Java.

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n²)	O(1)	Count overlaps per interval / pairwise active set.
Optimal (heap)	O(n log n)	O(n)	Sort by start; heap of end times; reuse rooms.
Optimal (two pointers)	O(n log n)	O(n)	Sort starts and ends; sweep concurrent count.