Meeting Rooms II

The problem

You are given a list intervals of n meetings (n is the length of intervals), each as [start, end]. Return the smallest number of rooms needed so every meeting can take place. A room that frees up at time 5 can host a meeting that starts at 5.

Example 1

Input: intervals = [[4, 8], [1, 5], [6, 9], [2, 6], [9, 11], [10, 12]]

Output: 3

At time 4, three meetings run at once: [1, 5], [2, 6] and [4, 8]. No moment has more.

meetings

at time 4

3 meetings

Example 2

Input: intervals = [[3, 7], [7, 9]]

Output: 1

The second starts exactly when the first ends, so one room is enough.

Example 3

Input: intervals = [[1, 10], [2, 3], [4, 5]]

Output: 2

[1, 10] keeps one room busy. The two short ones can share the other.

Constraints

• 1 ≤ n ≤ 10,000
• 0 ≤ start < end ≤ 1,000,000

Clarifying questions

Is back to back a clash?

No. A room free at 5 can take a meeting that starts at 5.

Are the meetings sorted?

No. They come in any order.

Do we need the room plan?

No, only how many rooms. That number equals the most meetings running at one moment.

Can meetings be moved?

No. Each meeting keeps its start and end.

Spot the pattern

Handing out rooms in start order is natural. For each new meeting, the only question is “has any room freed up?”, and the room that frees up first is the one to check. A min-heap of end times keeps that room on top. That is the heap pattern, used on intervals.

Solutions

Count at each startO(n²)Min-heap of end timesO(n log n)

Show all

Sorting the start times and the end times separately and sweeping them with two pointers is also O(n log n). It gives the same answer with a different picture.

Count at each start O(n²)

The idea

The number of rooms needed is the most meetings that run at the same moment. That moment is always the start of some meeting, because the count only goes up when a meeting starts.

So for each meeting’s start time start_time, count the meetings running at start_time: those with start ≤ start_time < end. The largest count is the answer.

Walkthrough

meetings

best

0

1. best = 0
2. for start_time, _ in intervals:
3. busy = 0
4. for start, end in intervals:
5. if start <= start_time < end: busy += 1
6. best = max(best, busy)
7. return best

The most rooms are needed at some moment when a meeting starts. So for each start time, count the meetings running at that moment.

← BackStep →Play1 / 8

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count at each start: the busiest moment is always some meeting's start.
    // For each start, count the meetings running then. O(n^2) time, O(1) memory.
    public int minMeetingRooms(int[][] intervals) {
        int best = 0;
        for (int[] meeting : intervals) {
            int startTime = meeting[0], busy = 0;
            for (int[] interval : intervals) {
                // start <= startTime < end: a meeting that ends at startTime has already left.
                if (interval[0] <= startTime && startTime < interval[1]) busy++;
            }
            best = Math.max(best, busy);
        }
        return best;
    }
}

Big O

Time O(n²)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit line checks if one meeting is running at time start_time. It sits inside two loops: one over the start times and one over all meetings. One check is 1 step.

   1. best = 0
   2. for start_time, _ in intervals:
   3. busy = 0
   4. for start, end in intervals:
   5. if start <= start_time < end: busy += 1
   6. best = max(best, busy)
   7. return best

2. 2 Count the runs on Example 1

   Example 1 has 6 meetings. Each of the 6 start times checks all 6 meetings.

   6 × 6 = 36 checks.

   start	t = 4	t = 1	t = 6	t = 2	t = 9	t = 10
   checks	6	6	6	6	6	6
   busy	3	1	2	2	1	2

   total

   6 × 6 = 36 checks

3. 3 Write the count for any n

   n × n = n²

   Check it with Example 1: 6 × 6 = 36.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is already n².

   So the time is O(n²).

5. S Space: count the extra memory the same way

   The code keeps best and busy. The space is O(1).

   bestbusy

Min-heap of end times O(n log n)

The idea

Sort the meetings by start. Keep a min-heap ends with the end time of every room in use. Its top is the room that frees up first.

For each meeting, in start order:

• If the top room ends no later than this meeting starts, that room is free. Pop it and reuse it.
• Otherwise every room is still busy, because the top one frees up first. Use a new room.

Either way, push this meeting’s end time. At the end, the heap size is the number of rooms.

Why it is correct: a new room is opened only when even the earliest-freeing room is busy. Then all rooms are busy at this start time, so that many meetings truly overlap, and no plan can use fewer.

Walkthrough

meetings

rooms in use: end times smallest first

empty

1. intervals.sort(key=lambda interval: interval[0])
2. ends = [] # min-heap of end times
3. for start, end in intervals:
4. if ends and ends[0] <= start:
5. heappop(ends) # that room is free again
6. heappush(ends, end)
7. return len(ends)

The meetings are in no order. We will hand out rooms in time order.

← BackStep →Play1 / 9

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Min-heap of end times: hand out rooms in start order. The heap top is the
    // room that frees up first. Sort plus n heap steps: O(n log n) time, O(n) memory.
    public int minMeetingRooms(int[][] intervals) {
        java.util.Arrays.sort(intervals, (first, second) -> Integer.compare(first[0], second[0]));
        java.util.PriorityQueue<Integer> ends = new java.util.PriorityQueue<>();
        for (int[] interval : intervals) {
            // The room that frees up first is free by now: reuse it.
            if (!ends.isEmpty() && ends.peek() <= interval[0]) ends.poll();
            ends.add(interval[1]);
        }
        // One end time per room ever opened.
        return ends.size();
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two parts repeat. The sort compares meetings many times. Then each run of the loop does at most one pop and one push. On a heap of size up to n, each costs about log₂ n steps.

   1. intervals.sort(key=lambda interval: interval[0])
   2. ends = [] # min-heap of end times
   3. for start, end in intervals:
   4. if ends and ends[0] <= start:
   5. heappop(ends) # that room is free again
   6. heappush(ends, end)
   7. return len(ends)

2. 2 Count the runs on Example 1

   Example 1 has 6 meetings. Sorting 6 items takes about 6 × log₂ 6, so about 16 steps. The loop then does 6 pushes and 3 pops, on a heap that never holds more than 3.

   About 16 + 9 heap operations.

   meeting	[1, 5]	[2, 6]	[4, 8]	[6, 9]	[9, 11]	[10, 12]
   heap work	push	push	push	pop + push	pop + push	pop + push
   heap size	1	2	3	3	3	3

3. 3 Write the count for any n

   The sort costs n log₂ n. The loop does at most 2 heap operations per meeting, each about log₂ n:

   n log₂ n + 2n log₂ n = 3n log₂ n

   Check it with Example 1: the loop did 9 heap operations, within the 2 × 6 = 12 allowed. Each was on a heap of at most 3, so it was cheaper than log₂ 6.

4. 4 Keep only the part that grows fastest

   Drop the 3. What is left is n log n. Both the sort and the heap work grow at that rate.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The heap can hold one end time per meeting, when they all overlap. The space is O(n).

   ends (up to n end times)

Common mistake

Checking only the last room opened

The room that frees up first is not always the newest one. In [[1, 3], [2, 10], [4, 5]], the last room opened is busy until 10, so checking it opens a third room. But the first room is free at 3. The heap always checks the room that frees up first.

Tested at the limits

2,000 random lists of 1 to 7 meetings with times from 0 to 10, so back-to-back meetings and overlaps both come up often. Count at each start and the min-heap of end times gave the same answer every time.

Largest inputs	Result
10,000 meetings (the most allowed), all running at the same moment, so each one needs its own room. Min-heap of end times.	0.003 s, and about 0.15 MB of extra memory: the heap holds all 10,000 end times, plus the sort.
2,000 meetings, all overlapping. Count at each start.	0.17 s. At 10,000 meetings it would make 100 million checks.