Frequently Asked at Uber — This problem has been reported multiple times in recent Uber L5A interviews.

Meeting Rooms II

Problem Statement

Given an array of meeting time intervals intervals[i] = [start_i, end_i], return the minimum number of conference rooms required. Assume end is exclusive — a meeting ending at time t frees the room for a meeting starting at time t.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: One room holds [0,30]; the second holds [5,10] then [15,20].

Example 2:

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

Constraints:

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

Difficulty: Medium

---

Pattern Recognition

• What is the structure of the input? A list of [start, end] intervals.
• What are we optimizing? Minimum number of "resources" needed to cover all intervals given concurrency constraints.
• What pattern does this suggest? Either sweep-line on start/end events, or a min-heap of end times over intervals sorted by start.
• Why does this pattern fit? The number of rooms at any moment equals the number of currently-active meetings. The heap tracks "when is the next room freed?" and lets you reuse rooms lazily.

---

Approach

Brute Force — For each interval, check overlaps with all prior

For each interval, scan all previous intervals to count overlaps, then track the max overlap count.

Time: O(N^2). Space: O(1). Why insufficient: N up to 10^4 gives 10^8 ops — slow.

Optimal — Min-Heap of End Times

Key Insight: Sort meetings by start time. A min-heap of active rooms' end times tells you, at each new meeting start, whether the earliest-ending room is free. If it is (heap[0] <= currentStart), reuse it. Otherwise allocate a new one.

Step-by-step:

1. Sort intervals by start time.
2. For each [start, end]:
   • If the heap is non-empty and heap.top() <= start, pop it (that room just freed up).
   • Push end (the current meeting's end time).
3. The heap's final size is the peak concurrent meetings — the answer.

Time: O(N log N) — sort plus heap ops. Space: O(N) for the heap.

Alternative — Sweep Line

Sort start times and end times separately. Walk both with two pointers: if the next start is before the next end, we need one more room; else free one. Track the max.

Same complexity, often cleaner to reason about.

---

Walkthrough

intervals = [[0,30], [5,10], [15,20]] (already sorted).

Step	Meeting	Heap before	Top <= start?	Heap after	Rooms
1	[0,30]	[]	n/a	[30]	1
2	[5,10]	[30]	30 <= 5? no	[10, 30]	2
3	[15,20]	[10, 30]	10 <= 15? yes — pop, push 20	[20, 30]	2

Max heap size = 2. Answer: 2.

---

Implementation

TypeScript

function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
  // Simple heap via array (for brevity). In interview, note O(log N) with real heap.
  const heap: number[] = [];
  const pushHeap = (v: number) => {
    heap.push(v);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] <= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const popHeap = (): number => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      for (;;) {
        const l = 2*i+1, r = 2*i+2;
        let smallest = i;
        if (l < heap.length && heap[l] < heap[smallest]) smallest = l;
        if (r < heap.length && heap[r] < heap[smallest]) smallest = r;
        if (smallest === i) break;
        [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
        i = smallest;
      }
    }
    return top;
  };

  for (const [start, end] of intervals) {
    if (heap.length && heap[0] <= start) popHeap();
    pushHeap(end);
  }
  return heap.length;
}

C++

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> pq;
        for (auto& iv : intervals) {
            if (!pq.empty() && pq.top() <= iv[0]) pq.pop();
            pq.push(iv[1]);
        }
        return pq.size();
    }
};

Watch out: Forgetting to sort by start. The heap invariant depends on processing in chronological order.

Watch out: end == start — back-to-back meetings should reuse a room. Use <= in the pop check.

Watch out: JavaScript has no built-in heap. In an interview, acknowledge this and either implement one or use the sweep-line alternative.

---

Complexity Analysis

	Time	Space
Brute Force (pairwise overlap)	O(N^2)	O(1)
Heap	O(N log N)	O(N)
Sweep Line	O(N log N)	O(N)

Bottleneck: The sort dominates both optimal approaches.

---

Edge Cases

1. Single meeting — Answer is 1.
2. All disjoint meetings — Answer is 1 (one room is reused).
3. All overlapping meetings — Answer equals intervals.length.
4. Back-to-back [[1, 5], [5, 10]] — Answer is 1 because the first ends exactly when the second starts.
5. Zero-length intervals [[3, 3]] — Edge case; depending on interpretation, may need a room or not. Clarify.

---

Related Problems

• LC 252 — Meeting Rooms: Boolean can-attend-all version (sort, check no overlap).
• LC 1094 — Car Pooling: Sweep-line with per-event passenger delta.
• LC 1235 — Maximum Profit in Job Scheduling: DP + binary search over sorted intervals.
• LC 731 — My Calendar II: Maintain overlap count to reject triple bookings.

---

What Is Expected at Each Level?

Junior / New Grad: Recognize interval overlap and reach the O(N^2) pairwise approach. With a hint, sort and use a heap.

Mid-level: Jump directly to the sort + heap approach, explain the invariant, and handle the <= edge case correctly.

Senior: Offer both heap and sweep-line solutions and discuss when each is preferred. Generalize to "return the schedule with room assignments" by tagging heap entries with room IDs. Discuss integer-bucket sweep when times have bounded integer range.