Meeting Rooms II

Meeting Rooms II is the question that separates people who memorize from people who think. Meeting Rooms only asked yes or no. This one asks how many rooms you need so no meeting clashes. The answer is the largest number of meetings happening at the same time. Finding that peak is the real puzzle.

🎯 The Problem

You get a list of meetings and find the fewest rooms needed.

• Each meeting is a pair: a start time and an end time.
• Find the smallest number of rooms so no two meetings clash.
• Two meetings clash when both are running at the same instant.
• The answer is the peak overlap: the most meetings live at one moment.
• A meeting ending at 10 and another starting at 10 can share one room.

Input:  intervals = [[0, 30], [5, 10], [15, 20]]
Output: 2

Explanation: At time 5, the meetings [0, 30] and [5, 10] are both live.
That is two at once, so two rooms are enough for the whole day.

Here is the input drawn on a number line. Around time 5 to 10, two meetings run together, and that is the peak.

🐢 Approach 1: Count At Every Time Point (Brute Force)

Walk the clock and count live meetings at each tick.

The idea:

• Step over every time point on the clock.
• At each point, count how many meetings are live.
• The largest count you see is the answer.

Why it is weak:

• The clock can be huge. Times may go up to a million.
• For each tick you scan all meetings.
• The cost depends on how big the numbers are, not just the meeting count.

Here is the sweep-every-time-point code:

def min_meeting_rooms(intervals):
    if not intervals:
        return 0

    first = min(start for start, end in intervals)
    last = max(end for start, end in intervals)
    best = 0

    for time in range(first, last + 1):
        active = sum(start <= time < end for start, end in intervals)
        best = max(best, active)
    return best

⚡ Approach 2: Min-Heap Of End Times (Better)

The idea in one line: keep the rooms in use as a min-heap of their end times.

The idea:

• Sort the meetings by start time.
• A min-heap always hands you the smallest value fast.
• Here the smallest value is the room that frees up soonest.

How it works:

• For each meeting, look at the heap top, the earliest end.
• If that end is at or before this start, that room is free, so pop it.
• Push this meeting’s end, because it takes a room.
• The heap size right now is the rooms in use. Track its peak.

Why it is fast:

• Sorting is O(n log n). Each heap push and pop is O(log n).
• Done n times, the total stays O(n log n).

Here is the min-heap code for that idea:

import heapq


def min_meeting_rooms(intervals):
    intervals.sort()
    rooms = []

    for start, end in intervals:
        if rooms and rooms[0] <= start:
            heapq.heappop(rooms)
        heapq.heappush(rooms, end)

    return len(rooms)

⚡ Approach 3: Split Starts And Ends (Best)

The idea in one line: sort starts and ends apart, then sweep both with two pointers and no heap.

The idea:

• Take all start times into one list and all end times into another.
• Sort both lists.
• Sweep through time with two pointers.

How it works:

• Walk the starts in order. Compare each start with the smallest end not yet passed.
• If the start is before that end, a new meeting begins while an old one runs, so add a room and track the peak.
• If the start is at or after that end, an old meeting freed a room first, so reuse it and move the end pointer forward.

Why it is fast:

• Two sorts cost O(n log n). The sweep is O(n).
• No heap structure to maintain.

Here is the heap version as a flow.

Steps to Solve

1. Sort the meetings by start time.
2. Make an empty min-heap that will hold end times.
3. For each meeting, if the smallest end in the heap is at or before this start, pop it, because that room is free.
4. Push this meeting’s end onto the heap.
5. The current heap size is the rooms in use. Track the largest size you see.
6. Return that largest size.

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) {
    return (*(int *)a) - (*(int *)b);
}

int main(void) {
    int starts[] = {0, 5, 15};
    int ends[] = {30, 10, 20};
    int n = 3;

    qsort(starts, n, sizeof(int), cmp);  // sort start times
    qsort(ends, n, sizeof(int), cmp);    // sort end times

    int rooms = 0, peak = 0;
    int s = 0, e = 0;
    while (s < n) {
        if (starts[s] < ends[e]) {  // a meeting starts before one ends
            rooms++;                // need another room
            if (rooms > peak) peak = rooms;
            s++;
        } else {                    // a meeting freed a room first
            rooms--;
            e++;
        }
    }

    printf("%d\n", peak);
    return 0;
}

2

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());  // sort by start
    // min-heap: smallest end on top
    priority_queue<int, vector<int>, greater<int>> heap;

    int rooms = 0;
    for (auto& meeting : intervals) {
        if (!heap.empty() && heap.top() <= meeting[0]) {
            heap.pop();           // a room frees up
        }
        heap.push(meeting[1]);    // this meeting takes a room
        rooms = max(rooms, (int)heap.size());
    }
    return rooms;
}

int main() {
    vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
    cout << minMeetingRooms(intervals) << endl;
    return 0;
}

2

import java.util.Arrays;
import java.util.PriorityQueue;

public class MeetingRoomsII {
    public static int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);  // sort by start
        PriorityQueue<Integer> heap = new PriorityQueue<>();  // min-heap of ends

        int rooms = 0;
        for (int[] meeting : intervals) {
            if (!heap.isEmpty() && heap.peek() <= meeting[0]) {
                heap.poll();             // a room frees up
            }
            heap.add(meeting[1]);        // this meeting takes a room
            rooms = Math.max(rooms, heap.size());
        }
        return rooms;
    }

    public static void main(String[] args) {
        int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
        System.out.println(minMeetingRooms(intervals));
    }
}

2

import heapq


def min_meeting_rooms(intervals):
    intervals.sort(key=lambda block: block[0])  # sort by start
    heap = []  # min-heap of end times
    rooms = 0

    for start, end in intervals:
        if heap and heap[0] <= start:   # earliest room is free
            heapq.heappop(heap)
        heapq.heappush(heap, end)       # this meeting takes a room
        rooms = max(rooms, len(heap))   # track the peak
    return rooms


intervals = [[0, 30], [5, 10], [15, 20]]
print(min_meeting_rooms(intervals))

2

function minMeetingRooms(intervals) {
  const starts = intervals.map((b) => b[0]).sort((a, b) => a - b);
  const ends = intervals.map((b) => b[1]).sort((a, b) => a - b);

  let rooms = 0;
  let peak = 0;
  let s = 0;
  let e = 0;
  while (s < starts.length) {
    if (starts[s] < ends[e]) {  // a meeting starts before one ends
      rooms++;                  // need another room
      peak = Math.max(peak, rooms);
      s++;
    } else {                    // a room freed first
      rooms--;
      e++;
    }
  }
  return peak;
}

const intervals = [[0, 30], [5, 10], [15, 20]];
console.log(minMeetingRooms(intervals));

2

Now let us walk through the Python heap version line by line and see why each part is written this way.

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda block: block[0])
    heap = []
    rooms = 0

We sort by start so we meet the meetings in time order. The heap will hold the end times of meetings that are currently using a room. rooms will remember the most rooms we ever needed at once.

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)

For each meeting we look at heap[0], which in a min-heap is always the smallest end time, the room that frees up soonest. The check heap[0] <= start reads as “that room is already free by the time this meeting starts.” So we pop it, because we can reuse that room. We use <= because a meeting ending exactly at this start has already finished.

        heapq.heappush(heap, end)
        rooms = max(rooms, len(heap))
    return rooms

Every meeting needs a room, so we always push its end onto the heap. We did the pop first so a freed room gets reused instead of adding a new one. The heap size right now is the number of rooms in use, so we update rooms with the peak. At the end rooms holds the most rooms ever needed, which is the answer.

⏱️ Time and Space Complexity

The brute force over every time point depends on how large the times are, so it can be very slow. The heap version sorts in O(n log n) and does n heap operations each O(log n), so the total is O(n log n). The split-events version sorts two lists in O(n log n) then sweeps in O(n), so it is also O(n log n). Both use O(n) extra space for the heap or the event lists. The deep idea is that the answer is the peak overlap, the most meetings live at once.

🧩 Key Takeaways

• ✅ The answer is the peak overlap, the most meetings live at the same time.
• ✅ Sort by start so you meet the meetings in time order.
• ✅ A min-heap of end times tells you the room that frees up soonest.
• ✅ Reuse a room when its end is at or before the next start.
• ✅ The heap size at its largest is the number of rooms you need.

🚀 What’s Next?

• Meeting Rooms
• Insert Interval