Meeting Rooms II

Q: What is the time complexity of Meeting Rooms II?

Both fast solutions run in O(n log n) . The heap version sorts the meetings and does one O(log n) heap operation per meeting; the two-list version does two sorts and one O(n) walk. Both use O(n) extra space. Counting the running meetings at every start is O(n²) .

MediumIntervals Heap Sorting

+10

You get a list of meetings as two arrays: meeting i runs from starts[i] to ends[i]. A room holds one meeting at a time, and a meeting may start in a room at the exact moment another meeting there ends.

Write a function named minMeetingRooms that returns the smallest number of rooms that can hold all the meetings.

Function

minMeetingRooms(starts: integer-array, ends: integer-array) → integer

startsinteger-array: the start time of each meeting
endsinteger-array: the end time of each meeting, at the same index as its start
Returnsinteger: the fewest rooms that can hold every meeting

Constraints

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
The meetings are not sorted. Two meetings may be identical.

Examples

Input: starts = [4, 1, 7, 2]ends = [8, 5, 9, 6]
Output: 3
Explanation: At time 4 the meetings from 1 to 5, from 2 to 6 and from 4 to 8 are all running, so you need at least 3 rooms. Three are enough: the meeting from 7 to 9 takes the room that frees up at 5.

Input: starts = [0, 2, 3]ends = [10, 3, 5]
Output: 2
Explanation: The meeting from 0 to 10 keeps one room busy the whole time. The meeting from 2 to 3 needs a second room, and the meeting from 3 to 5 takes that same room as it frees up, so 2 rooms are enough.

+17 hidden tests on Submit

Follow-up

Can you also say which room each meeting goes to, using no more rooms than the answer?

Solution

The number of rooms you need is the largest number of meetings running at the same moment. Counting the running meetings at every start time finds it in O(n²). Sorting turns the question into one walk through the day: a min-heap of the times the rooms free up, or two sorted lists of starts and ends, gives the answer in O(n log n).

Count the meetings running at each start

Correct, but does not finish on the largest tests

Intuition

At any moment, every meeting that is running needs a room of its own. So you need at least as many rooms as the largest number of meetings running at once. That many is also enough: hand out rooms in order of start time, and a new room only opens when every room is busy, which means that many meetings are running right then.

The number of running meetings only goes up when a meeting starts, so the busiest moment is the start of some meeting. For each meeting i, count the meetings j with starts[j] ≤ starts[i] < ends[j]: they have begun and not yet ended. A meeting that ends exactly at starts[i] is not counted, because its room is free again at that moment.

In the first example, at time 4 the meetings from 1 to 5, from 2 to 6 and from 4 to 8 are running: 3. At time 7 only the meetings from 4 to 8 and from 7 to 9 are: 2. The largest count is 3.

Every one of the n meetings scans all n meetings. With n = 5000 that is 25 million checks: a fraction of a second in C, several seconds in Python or R, and four times more every time n doubles.

Algorithm

For each meeting i, set running to 0.
For each meeting j, add 1 to running when starts[j] ≤ starts[i] < ends[j].
Keep the largest value of running you have seen.
Return that largest value.

def minMeetingRooms(starts, ends):
    n = len(starts)
    most = 0
    for i in range(n):
        # how many meetings are running at the moment meeting i starts
        running = 0
        for j in range(n):
            if starts[j] <= starts[i] < ends[j]:
                running += 1
        most = max(most, running)
    return most

Min-heap of the times rooms free up

Intuition

Assign rooms the way a person at a front desk would. Take the meetings in order of start time. For each one, look at the room that frees up first. If it is free by the time the meeting starts, the meeting gets that room. If not, every room is still busy, so you open a new one.

Checking only that one room is safe. If the room that frees up first is still busy, all of them are. If it is free, any free room is as good as another: the meetings still to come start at this time or later, so every room that is free now stays free for all of them.

You need the earliest free time among the rooms, and it changes after every meeting. A min-heap keeps one end time per room and hands you the smallest. Reusing a room replaces its end time with the new meeting's end; opening a room pushes a new end time. In the first example, sorted by start: 1 to 5 gives [5], 2 to 6 gives [5, 6], 4 to 8 gives [5, 6, 8], and 7 to 9 finds 5 at or before 7 and replaces it, leaving [6, 8, 9]. Three rooms.

Sorting costs O(n log n) and each meeting does one heap operation of O(log n). Python's heapq, Java's PriorityQueue, C++'s priority_queue with greater, Rust's BinaryHeap with Reverse, Go's container/heap and PHP's SplMinHeap give you the heap. In the other languages you keep it in an array: the parent of index i is at (i-1)/2, and a value moves up while it is smaller than its parent.

Algorithm

Sort the meetings by start, keeping each start with its own end.
For each meeting, if the heap is not empty and its smallest end is at or before the meeting's start, replace that end with the meeting's end.
Otherwise push the meeting's end: a new room opens.
Return the size of the heap, one entry per room.

import heapq


def minMeetingRooms(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    free_at = []  # a min-heap: when each room's last meeting ends
    for start, end in meetings:
        if free_at and free_at[0] <= start:
            heapq.heapreplace(free_at, end)  # the earliest free room is free now: reuse it
        else:
            heapq.heappush(free_at, end)  # every room is busy: open a new one
    return len(free_at)

Sort starts and ends separately

Intuition

The heap remembers which end time belongs to which room, but the answer is only a count. When a meeting starts, all that matters is whether some meeting has ended by then and left a room free; which meeting it was does not matter. So sort the starts and the ends as two separate lists and walk through the starts, with a pointer ended into the ends.

For each start in order: if it is at or after endTimes[ended], a meeting has finished by then. Its room takes the new meeting, and ended moves on. Otherwise every room in use is still busy, and rooms grows by one. Each start uses up at most one end, the same way a reused room in the heap swaps one old end for one new end.

In the first example the starts are 1, 2, 4, 7 and the ends 5, 6, 8, 9. Starts 1, 2 and 4 all come before end 5, so rooms climbs to 3. Start 7 is at or after 5, so it reuses that room and ended moves to end 6. The answer is 3. The ≥ is where touching meetings share a room: in the second example, start 12 meets end 12 and reuses it.

The count never goes past the true peak: when rooms grows, the next end is still in the future, so all rooms meetings are running at that moment. It also reaches the peak, because a start only skips opening a room when a real end at or before it has freed one. Two sorts cost O(n log n), the walk O(n), and the sorted copies O(n) space.

Algorithm

Sort a copy of the starts and a copy of the ends.
Set rooms and ended to 0.
For each start in order, if it is at or after endTimes[ended], add 1 to ended: the meeting takes a freed room.
Otherwise add 1 to rooms.
Return rooms.

def minMeetingRooms(starts, ends):
    start_times = sorted(starts)
    end_times = sorted(ends)
    rooms = 0
    ended = 0  # how many meetings have ended, earliest end first
    for start in start_times:
        if start >= end_times[ended]:
            ended += 1  # a meeting has ended by now: this one takes its room
        else:
            rooms += 1  # every room is busy: open a new one
    return rooms

Pitfalls and edge cases

Most bugs are in the comparison at a touching moment or in which room gets checked.

Checking start > end instead of start ≥ end. Then a meeting cannot use a room the moment it frees, and the meetings from 10 to 12, 12 to 14 and 14 to 16 take 2 rooms instead of 1.
Checking the room you opened last instead of the room that frees up first. For the meetings from 1 to 3, 2 to 10 and 4 to 6, the last room opened is busy until 10, so you open a third room while the first one has been free since 3.
Taking the largest number of meetings that overlap one meeting, plus one. The meeting from 0 to 10 overlaps the meetings from 2 to 3 and from 3 to 5, but those two do not overlap each other, so 2 rooms are enough, not 3.
Mixing up the two sorted approaches. The heap needs each end paired with its own start before sorting by start; the two-list approach sorts the starts and the ends apart on purpose.

Frequently asked questions4

What is the time complexity of Meeting Rooms II?

Both fast solutions run in O(n log n). The heap version sorts the meetings and does one O(log n) heap operation per meeting; the two-list version does two sorts and one O(n) walk. Both use O(n) extra space. Counting the running meetings at every start is O(n²).

Why does a min-heap solve Meeting Rooms II?

Taking meetings in start order, the only room worth checking is the one that frees up first. A min-heap of end times gives you that room in O(1) and updates in O(log n). The heap grows only when every room is busy, so its final size is the fewest rooms that work.

Can Meeting Rooms II be solved without a heap?

Yes. Sort the start times and the end times as two separate lists and walk the starts with a pointer into the ends. A start at or after the next unused end reuses a room; any other start opens one. The same idea works as a sweep line: turn each meeting into a +1 event at its start and a -1 event at its end, process ends before starts at equal times, and track the largest running total.

Is the answer the same as the most meetings that overlap at one time?

Yes. Meetings running at the same moment need different rooms, so you need at least that many. Handing each meeting, in start order, any room that is free never needs more, so the peak number of overlapping meetings is exactly the answer.

Python

def minMeetingRooms(starts, ends):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

starts = [4, 1, 7, 2]
ends = [8, 5, 9, 6]

Expected

Meeting Rooms II

Function

Constraints

Examples

Hints

Solution

Count the meetings running at each start

Min-heap of the times rooms free up

Sort starts and ends separately

Pitfalls and edge cases

Frequently asked questions4

Similar problems