Meeting Rooms II

35 min · minMeetingRooms()

One room solves an empty afternoon. A busy calendar may need a whole floor.

You're given intervals, where each [start, end] pair is one meeting. Return the minimum number of rooms needed so that every meeting can happen on schedule.

That number is the largest number of meetings active at the same moment:

A meeting uses its room from start up to, but not including, end.
When one meeting ends at time 5 and another starts at 5, they can reuse the same room. Touching endpoints aren't simultaneous.
Every meeting has positive duration: start < end.

Constraints

1 <= intervals.length <= 100_000
Every interval contains exactly two integers: [start, end].
0 <= start < end <= 1_000_000_000

Hints

Watch the room count change

A start time consumes one room. An end time releases one. If you process those changes chronologically, the highest running count is the answer.

Settle ties correctly

When an end and a start share a timestamp, process the end first. The old meeting gives up its room before the new meeting asks for one.

You only need two sorted lists

Sort all starts and all ends separately. Walk the starts from left to right while advancing past every end that is less than or equal to the next start.

Follow-up

Could you also assign a room number to every meeting while still using the minimum?

Visible cases

Examples

Example 1

ready

Input: intervals = [ [ 0, 30 ], [ 5, 10 ], [ 15, 20 ] ]
Expected: 2
Why: at most two meetings run at once

Example 2

ready

Input: intervals = [ [ 7, 10 ], [ 2, 4 ] ]
Expected: 1
Why: the meetings never overlap, so one room is reusable

Example 3

ready

Input: intervals = [ [ 1, 5 ], [ 5, 10 ], [ 10, 15 ] ]
Expected: 1
Why: each room is released exactly when the next meeting starts

Interview signal

Asked at

AmazonGoogleUber

Sorted event sweep

Turn each meeting into two events: +1 at its start and -1 at its end. A sweep processes those events from earliest to latest while keeping a running room count. Sort ends before starts when their times tie, because the same room can be handed over at that instant.

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    events: list[tuple[int, int]] = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
 
    events.sort(key=lambda event: (event[0], event[1]))
 
    active = 0
    most_active = 0
    for _, change in events:
        active += change
        most_active = max(most_active, active)
    return most_active

Time O(n log n) to sort 2n events. Space O(n) for the event list.

Separate starts and ends

The event list stores a label beside every timestamp, but sorted position already tells us which list a time came from. Sort starts and ends independently. Before opening a room for the next start, release every meeting whose end is at or before that start.

def min_meeting_rooms(intervals: list[list[int]]) -> int:
    starts = sorted(start for start, _ in intervals)
    ends = sorted(end for _, end in intervals)
 
    active = 0
    most_active = 0
    end_index = 0
 
    for start in starts:
        while end_index < len(ends) and ends[end_index] <= start:
            active -= 1
            end_index += 1
        active += 1
        most_active = max(most_active, active)
 
    return most_active

Using ends[end_index] <= start is the key tie rule. Finished meetings release their rooms before the current meeting begins. Each start and end advances once after sorting.

Time O(n log n) for the two sorts, then O(n) for the merge. Space O(n) for the two sorted arrays.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrayintervals: int[][]

Expected

Run: visible + custom · Submit: full suite