Blind Plus 100 Visualized

#67 · Intervals

Meeting Rooms II

Given meeting time intervals [start, end), return the minimum number of conference rooms required so that every meeting has a room.

MediumLeetCode
  • Being examined
  • New / inserted
  • Kept / merged / answer
  • Removed / conflict
  • Untouched
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Sweep line with a counter

The number of rooms needed equals the largest number of meetings running at the same moment. Turning each meeting into a +1 at its start and a −1 at its end, then walking through time in order while adding the deltas, gives that number as the maximum of the running total.

Memory layout

An array of 2n (time, ±1) events, or two sorted arrays of starts and ends.

OperationCost
timeO(n log n)
spaceO(n)

Min-heap of room end times

Process meetings in start order and keep a min-heap of the end times of rooms in use. If the earliest-ending room is free by the next start, reuse it (replace its end time); otherwise add a new room. The heap size at the end is the answer.

Memory layout

A binary heap of at most k integers (k = rooms).

OperationCost
time / spaceO(n log k) / O(k)

Why it fits

  • Every room-assignment strategy is limited by the busiest moment: if m meetings overlap somewhere, m rooms are needed, and m rooms always suffice.
  • So the problem is about maximum overlap, which a counter over sorted events computes directly.
  • Reusing a freed room when a meeting starts exactly at the end of another matches the half-open meaning of intervals.

Why alternatives degrade

Colouring the interval graph by brute force:
It is the same answer (the clique number), but search over assignments is exponential.
Counting meetings per start time:
It ignores meetings that began earlier and are still running.
Checking every pair:
Pairwise overlaps say nothing about how many meetings overlap at the same instant.

Four approaches, from naive to production

1 · beginner

Give each meeting the first free room

time O(n log n + n · rooms)space O(rooms)

Sort by start. For each meeting scan the open rooms for one that has become free and reuse it; if none is free open a new room. The final number of rooms is the answer.

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    vector<int> roomEnds;
    for (auto& iv : sorted) {
        int start = iv[0], end = iv[1];
        bool placed = false;
        for (size_t r = 0; r < roomEnds.size(); r++) {
            if (roomEnds[r] <= start) {
                roomEnds[r] = end;
                placed = true;
                break;
            }
        }
        if (!placed) roomEnds.push_back(end);
    }
    return roomEnds.size();
}

Flaws & bottlenecks

  • Every meeting scans all open rooms: quadratic when many rooms are needed.
  • It tracks assignments although only the count matters.
  • The scan finds any free room, not the earliest-freed one; the count is still right, but it gives no insight into why.

Interviewer cross-questions

Why does assigning in start order never use more rooms than necessary?

Say: When a meeting starts and every open room is still busy, all those meetings overlap it, so that many rooms are needed at that moment anyway. A new room is only opened exactly when the overlap count increases.

How could the scan be faster?

Say: Keep the room end times in a min-heap: only the earliest end time ever matters, and it is at the top.

Is the order of the rooms important?

Say: No, any free room works. All free rooms are interchangeable for the rest of the schedule.

2 · intermediate

Sweep line over start and end events

time O(n log n)space O(n)

Create a +1 event at every start and a −1 event at every end, sort by time (ends before starts at the same time), and keep a running total. The highest running total is the number of rooms.

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<array<int, 2>> events;
    for (auto& iv : intervals) { events.push_back({iv[0], 1}); events.push_back({iv[1], -1}); }
    sort(events.begin(), events.end());
    int current = 0, best = 0;
    for (auto& ev : events) {
        current += ev[1];
        best = max(best, current);
    }
    return best;
}

Flaws & bottlenecks

  • Doubles the number of items to sort and allocates an array per event.
  • The tie-break (end before start at the same time) is easy to get wrong.
  • It computes the maximum overlap but not a room assignment.

Interviewer cross-questions

Why does the order at equal times matter?

Say: A meeting ending at 10 and another starting at 10 can share a room. If the start were processed first, the counter would briefly count both and overstate the rooms needed.

Can you also report the room assignment?

Say: Yes, with the heap approach: keep (end, room id) pairs and reuse the id of the room that frees up.

What does the sweep give you besides the answer?

Say: The whole occupancy curve, so you can see when the rooms are busiest or compute the total room-hours.

3 · advanced

Two sorted lists and two pointers

time O(n log n)space O(n)

Sort the starts and the ends separately. For each start, if it is before the earliest unused end a new room is needed; otherwise a room has been freed and the end pointer advances.

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<int> starts, ends;
    for (auto& iv : intervals) { starts.push_back(iv[0]); ends.push_back(iv[1]); }
    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());
    int rooms = 0, e = 0;
    for (size_t s = 0; s < starts.size(); s++) {
        if (starts[s] < ends[e]) rooms++;
        else e++;
    }
    return rooms;
}

Flaws & bottlenecks

  • Less intuitive: the pairing between starts and ends is intentionally dropped.
  • rooms never decreases, which reads oddly until you see that it counts the peak.
  • Needs two sorted copies.

Interviewer cross-questions

Why can starts and ends be sorted separately?

Say: At any moment the number of running meetings is (starts so far) − (ends so far). That depends only on the two sorted lists, not on which end belongs to which start.

Why does rooms only grow?

Say: When a room frees up and the new meeting reuses it, the count in use is unchanged; the variable stores the peak, which is exactly the answer.

What does a start equal to an end do?

Say: The test is strictly less than, so equal values take the else branch and the freed room is reused, matching half-open intervals.

4 · expert

Difference array over time

time O(n + T)space O(T)

When times are small integers, add +1 at each start and −1 at each end in an array indexed by time, then take a prefix sum over time and keep the maximum. No sorting is needed.

int minMeetingRooms(vector<vector<int>>& intervals) {
    int maxTime = 0;
    for (auto& iv : intervals) maxTime = max(maxTime, iv[1]);
    vector<int> delta(maxTime + 2, 0);
    for (auto& iv : intervals) {
        delta[iv[0]]++;
        delta[iv[1]]--;
    }
    int current = 0, best = 0;
    for (int t = 0; t <= maxTime; t++) {
        current += delta[t];
        best = max(best, current);
    }
    return best;
}

Flaws & bottlenecks

  • T, the length of the time range, can be far larger than n (timestamps in milliseconds).
  • Allocates an array as long as the latest end time.
  • Impossible for fractional or huge times without coordinate compression, which brings back a sort.

Interviewer cross-questions

When does this beat the sort-based methods?

Say: When T is small compared with n log n, for example minute-granularity bookings within a day, or when the same range is reused for many queries.

How do you handle huge timestamps?

Say: Compress coordinates: sort the distinct times, map them to 0 … k−1 and use an array of size k. That is O(n log n) again, equal to the sweep line.

What is a difference array?

Say: An array of changes between neighbours. Adding +1 at the start and −1 at the end of a range, then taking prefix sums, reconstructs the count of overlapping ranges at every position in one pass.

Synchronized code walkthrough

Showing: Give each meeting the first free room — shares the player above; click any step to jump.

int minMeetingRooms(vector<vector<int>>& intervals) {
    vector<vector<int>> sorted = intervals; sort(sorted.begin(), sorted.end());
    vector<int> roomEnds;
    for (auto& iv : sorted) {
        int start = iv[0], end = iv[1];
        bool placed = false;
        for (size_t r = 0; r < roomEnds.size(); r++) {
            if (roomEnds[r] <= start) {
                roomEnds[r] = end;
                placed = true;
                break;
            }
        }
        if (!placed) roomEnds.push_back(end);
    }
    return roomEnds.size();
}