Frequently Asked at Google — This problem has been reported multiple times in recent Google L4 interviews.

Meeting Rooms II (LC 253)

Problem Statement

Given an array of meeting time intervals intervals[i] = [start_i, end_i], return the minimum number of conference rooms required to host all meetings without conflict.

Example 1:

Input:  [[0,30],[5,10],[15,20]]
Output: 2
Explanation: Room A hosts [0,30]; Room B hosts [5,10] then [15,20].

Example 2:

Input:  [[7,10],[2,4]]
Output: 1

Constraints:

• 1 <= intervals.length <= 10^4
• 0 <= start_i < end_i <= 10^6

Difficulty: Medium

---

Pattern Recognition

• Input structure: interval list.
• What are we optimizing? max simultaneity — i.e., the maximum number of intervals overlapping at any single time point.
• Pattern: two well-known techniques —
  1. Min-heap of end times after sorting by start.
  2. Sweep line using a sorted event list.
• Why: the answer equals the peak number of concurrently live meetings. The heap keeps "rooms currently in use"; the sweep line counts active events over time.

---

Approach

Brute Force

For each meeting, check against all prior to find free rooms. O(n^2). Acceptable for small n, cumbersome to code cleanly.

Approach 1 — Min-Heap

Key Insight: Sort meetings by start time. For each meeting, the earliest-ending room is the only candidate to reuse. If it is free (its end ≤ current start), reuse; otherwise, allocate a new room.

sort intervals by start
heap = []  // min-heap of end times
for [start, end] in intervals:
    if heap and heap.top() <= start:
        heap.pop()  // reuse
    heap.push(end)
return heap.size

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

Approach 2 — Sweep Line (Two Sorted Arrays)

Key Insight: Separate start and end times. Walk both pointers; a start before an end means a new room must open; a start at or after an end means a room is freed.

starts = sorted starts
ends = sorted ends
rooms = 0, peak = 0, j = 0
for i in 0..n-1:
    if starts[i] < ends[j]:
        rooms++
    else:
        j++        // a meeting ended; reuse its room, don't change room count
    peak = max(peak, rooms)
return peak

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

The sweep line is slightly faster in practice (only two sorts, no heap).

---

Walkthrough — Min-Heap

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

Interval	Heap before	Heap.top ≤ start?	Action	Heap after	Rooms
[0,30]	[]	n/a	push 30	[30]	1
[5,10]	[30]	30 ≤ 5? No	push 10	[10, 30]	2
[15,20]	[10, 30]	10 ≤ 15? Yes	pop 10, push 20	[20, 30]	2

Peak size = 2.

---

Walkthrough — Sweep Line

Starts: [0, 5, 15]. Ends: [10, 20, 30].

i	j	starts[i]	ends[j]	Action	rooms	peak
0	0	0	10	0 < 10, rooms++	1	1
1	0	5	10	5 < 10, rooms++	2	2
2	0	15	10	15 ≥ 10, j++	2	2

Answer: 2.

---

Implementation

TypeScript

// Min-Heap approach using array-backed priority queue
class MinHeap {
    private h: number[] = [];
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(x: number) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p] <= this.h[i]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): number {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < this.h.length && this.h[l] < this.h[s]) s = l;
                if (r < this.h.length && this.h[r] < this.h[s]) s = r;
                if (s === i) break;
                [this.h[i], this.h[s]] = [this.h[s], this.h[i]];
                i = s;
            }
        }
        return top;
    }
}

function minMeetingRooms(intervals: number[][]): number {
    if (intervals.length === 0) return 0;
    intervals.sort((a, b) => a[0] - b[0]);
    const heap = new MinHeap();
    for (const [start, end] of intervals) {
        if (heap.size() > 0 && heap.peek() <= start) heap.pop();
        heap.push(end);
    }
    return heap.size();
}

// Sweep line (often cleaner)
function minMeetingRoomsSweep(intervals: number[][]): number {
    const n = intervals.length;
    if (n === 0) return 0;
    const starts = intervals.map(x => x[0]).sort((a, b) => a - b);
    const ends = intervals.map(x => x[1]).sort((a, b) => a - b);
    let rooms = 0, peak = 0, j = 0;
    for (let i = 0; i < n; i++) {
        if (starts[i] < ends[j]) rooms++;
        else j++;
        peak = Math.max(peak, rooms);
    }
    return peak;
}

C++

int minMeetingRooms(vector<vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) { return a[0] < b[0]; });
    priority_queue<int, vector<int>, greater<int>> pq; // min-heap of end times
    for (auto& iv : intervals) {
        if (!pq.empty() && pq.top() <= iv[0]) pq.pop();
        pq.push(iv[1]);
    }
    return pq.size();
}

// Sweep line
int minMeetingRoomsSweep(vector<vector<int>>& intervals) {
    int n = intervals.size();
    if (n == 0) return 0;
    vector<int> starts(n), ends(n);
    for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    int rooms = 0, peak = 0, j = 0;
    for (int i = 0; i < n; i++) {
        if (starts[i] < ends[j]) rooms++;
        else j++;
        peak = max(peak, rooms);
    }
    return peak;
}

Watch out:

1. Using <= vs < for end-vs-start affects whether back-to-back meetings share a room. Standard LeetCode convention: meeting that ends at t can share a room with one starting at t. So use <= in the heap check and < in the sweep line's "new room needed" check.
2. In the sweep line, you do NOT decrement rooms when a meeting ends — you simply fail to increment. Keeping track of peak is what matters.
3. Forgetting to sort by start first in the heap approach gives nonsensical results.

---

Complexity Analysis

	Time	Space
Brute Force	O(n^2)	O(n)
Min-Heap	O(n log n)	O(n)
Sweep Line	O(n log n)	O(n)

Bottleneck: both optimal solutions are dominated by the sort. On a problem where intervals come in sorted by start, you can drop to O(n log k) where k = number of rooms (heap size).

---

Edge Cases

1. Empty input — return 0.
2. All meetings same start — rooms equal n; heap never pops.
3. Serial meetings ([0,5],[5,10],[10,15]) — one room; <= comparison saves you.
4. Single meeting — return 1.
5. Intervals with very large end values — both approaches are unaffected numerically.
6. Negative times — constraints forbid them but your comparisons still work if relaxed.

---

Related Problems

• LC 252 — Meeting Rooms — Just asks whether a conflict exists. O(n log n) sort + linear scan.
• LC 56 — Merge Intervals — Same sort-and-sweep foundation.
• LC 435 — Non-overlapping Intervals — Minimum removals; greedy by end time.
• LC 1229 — Meeting Scheduler — Two-pointer over sorted slots to find overlap.

---

What Is Expected at Each Level

Junior: Brute force or the heap approach with guidance. Explain why sorting by start matters.

Mid-level: Implement both heap and sweep-line versions, articulate the tradeoffs, handle the shared-endpoint edge correctly.

Senior (L4 target): Write both approaches, discuss when one beats the other (heap wins on streaming input, sweep line on pre-sorted bulk), generalize to k-resource scheduling, and connect to CPU-burst job scheduling. Call out the exact semantics of meeting-end = meeting-start transitions.