Meeting Rooms II

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

The heap and two-list solutions both run in O(n log n) time and O(n) extra space. The sorting dominates; the walk after it costs O(n log n) with the heap and O(n) with two lists.

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, 2 to 6 and 4 to 8 all run, so you need at least 3 rooms. Three are enough: the meeting from 7 to 9 takes the room freed at 5.

Input: starts = [0, 2, 3]ends = [10, 3, 5]
Output: 2
Explanation: The meeting from 0 to 10 holds one room throughout. The meetings from 2 to 3 and from 3 to 5 share a second room, so 2 rooms are enough.

Follow-up

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

Solution

You need as many rooms as the most meetings running at one moment. Counting the running meetings at every start costs O(n²). Sorting lets you walk through the day once, with a min-heap of the times rooms free up or with two sorted lists of starts and ends, in O(n log n).

Count the meetings running at each start

Correct, but does not finish on the largest tests

Intuition

The number of running meetings only rises when a meeting starts, so the busiest moment is some meeting's start. For each meeting i, count the meetings j with starts[j] ≤ starts[i] < ends[j]. A meeting that ends exactly at starts[i] is not counted: its room is free again. In the first example, time 4 has three running meetings and time 7 has two, so the answer is 3.

Every one of the n meetings scans all n: n = 5000 means 25 million checks.

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

Take the meetings in order of start time and look only at the room that frees up first. If it is still busy when the meeting starts, every room is, so you open a new one. If it is free, any free room is as good as another: the meetings still to come start no earlier, so a room free now stays free for all of them.

A min-heap keeps one end time per room and hands you the smallest. In the first example, sorted by start, the heap grows to [5, 6, 8]. The meeting from 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).

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 answer is a count, so at each start you only need to know whether some meeting has ended by then, not which one. Sort the starts and the ends as separate lists and walk the starts with a pointer ended into the ends. A start at or after endTimes[ended] takes that freed room; any other start opens one.

The count is exact. When rooms grows, the next end is still in the future, so all rooms meetings run at that moment. A start skips opening a room only when a real end at or before it has freed one. In the first example, starts 1, 2 and 4 all come before end 5, so rooms reaches 3, and start 7 reuses the room freed at 5. Two sorts cost O(n log n) and the walk O(n).

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

Checking start > end instead of start ≥ end. A meeting then 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 one that frees up first. For the meetings from 1 to 3, 2 to 10 and 4 to 6, you open a third room at 4 though the first has been free since 3.
Answering with the most meetings that overlap one meeting, plus one. The meeting from 0 to 10 overlaps the meetings from 2 to 3 and 3 to 5, but those two never overlap, so 2 rooms are enough.

Frequently asked questions3

What is the time complexity of Meeting Rooms II?

The heap and two-list solutions both run in O(n log n) time and O(n) extra space. The sorting dominates; the walk after it costs O(n log n) with the heap and O(n) with two lists.

Can Meeting Rooms II be solved with a sweep line?

Yes. Turn each meeting into a +1 event at its start and a -1 event at its end, sort the events, and track the largest running total. At equal times, process ends before starts so that touching meetings share a room.

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.

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

Test #1

Test #2

Test #3

Arguments

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

Expected Output

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 questions3

Similar problems