Meeting Rooms II

Frequently Asked at Salesforce OA — Reported repeatedly in Salesforce HackerRank OAs (2024-2026).

Problem Statement

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

Example 1:

Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2
Explanation: Meeting 1 runs 0-30. Meeting 2 (5-10) overlaps, so a 2nd room. 
             Meeting 3 (15-20) overlaps meeting 1 but not meeting 2 (which ended at 10), 
             so reuse room 2. Max concurrent = 2.

Example 2:

Input: intervals = [[7, 10], [2, 4]]
Output: 1
Explanation: The two meetings do not overlap; one room suffices.

Constraints:

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

Difficulty: Medium LC: 253 Round: Technical R1

---

Pattern Recognition

• What is the input structure? Array of intervals [start, end].
• What are we optimizing? Minimum room count = maximum number of intervals overlapping at any point in time.
• What pattern does this fit? Min-heap of end times, or sweep line over sorted events.
• Why does this pattern fit? When a new meeting starts, the only question is "has any earlier room freed up?" The earliest-freeing room is the heap min.

---

Approach

Brute Force — Check Every Pair

For each meeting, count how many others overlap it. Answer = max such count.

Time: O(n^2). Space: O(1). Why insufficient: Quadratic doesn't scale past ~10^4.

Optimal 1 — Min-Heap of End Times

Key Insight: Sort meetings by start. For each meeting, if the earliest-ending room is free by now (heap.top() <= start), reuse it (pop). Always push the new meeting's end. Answer = heap size at the end.

Step-by-step:

1. Sort intervals by start time.
2. Create an empty min-heap of end times.
3. For each [start, end]:
   • If heap is non-empty AND heap.top() <= start, pop (reuse that room).
   • Push end.
4. Return heap.size().

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

Optimal 2 — Sweep Line

Create events: (start, +1) and (end, -1). Sort (end before start on ties, so a 10-ending and 10-starting share a room). Scan, tracking max concurrent +1s.

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

---

Walkthrough (Min-Heap)

Trace on [[0, 30], [5, 10], [15, 20]]:

After sort by start: same order.

meeting	heap before	heap.top() <= start?	action	heap after
[0, 30]	[]	—	push 30	[30]
[5, 10]	[30]	30 <= 5? no	push 10	[10, 30]
[15, 20]	[10, 30]	10 <= 15? yes	pop, push 20	[20, 30]

Final heap size = 2. Answer: 2.

---

Implementation

TypeScript

function minMeetingRooms(intervals: number[][]): number {
    if (intervals.length === 0) return 0;
    intervals.sort((a, b) => a[0] - b[0]);

    // Min-heap of end times.
    const heap: number[] = [];
    const push = (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 pop = (): number => {
        const top = heap[0];
        const last = heap.pop()!;
        if (heap.length > 0) {
            heap[0] = last;
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < heap.length && heap[l] < heap[s]) s = l;
                if (r < heap.length && heap[r] < heap[s]) s = r;
                if (s === i) break;
                [heap[s], heap[i]] = [heap[i], heap[s]];
                i = s;
            }
        }
        return top;
    };

    for (const [start, end] of intervals) {
        // Reuse earliest-freeing room if available.
        if (heap.length > 0 && heap[0] <= start) pop();
        push(end);
    }
    return heap.length;
}

C++

#include <vector>
#include <queue>
#include <algorithm>

int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    std::sort(intervals.begin(), intervals.end());

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

Watch out:

1. heap.top() < start vs <=. If meeting A ends at 10 and meeting B starts at 10, they can share. Use <=.
2. Sorting by end time instead of start. You must process meetings in start order so that the heap's top reflects "will this meeting conflict with an already-running one?"
3. Empty input. Return 0.

---

Complexity Analysis

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

Bottleneck: The sort. Heap operations contribute a log factor but are dominated.

---

Edge Cases

1. Single meeting — 1 room.
2. All meetings identical ([[1,5], [1,5], [1,5]]) — n rooms.
3. Back-to-back meetings ([[1, 5], [5, 10]]) — 1 room (share at boundary).
4. Empty input — 0 rooms.
5. Meetings with start == end — degenerate (length 0). Problem usually excludes, but if allowed, they occupy a room instantaneously.

---

Related Problems

• LC 252 — Meeting Rooms — Boolean version: can one person attend all meetings?
• LC 56 — Merge Intervals — Related sort-and-scan pattern, different output.
• LC 435 — Non-overlapping Intervals — Min removal to make non-overlapping; greedy by end time.
• LC 1094 — Car Pooling — Sweep line variant on capacities.

---

Interview Strategy Notes

This is a Salesforce staple in Technical R1. Expect the interviewer to ask for both the heap approach and the sweep-line approach, or to push on the <= vs < decision. Code one, explain the other. Budget 15-20 minutes.

---

What is Expected at Each Level

Junior: Solves with the heap with some guidance. May need a hint about "what does the heap store?"

Mid-level: Implements cleanly. Discusses both heap and sweep-line. Handles back-to-back meetings correctly.

Senior: Offers both solutions, discusses the constant-factor tradeoff (sweep is faster in practice for small n), and extends to the "assign room names" variant where you output which room each meeting is in (stable assignment via a separate available-room heap).