~/problems / Intervals

Meeting Rooms II

medium ~25 min

Write min_meeting_rooms(intervals: list[list[int]]) -> int.

Each meeting is [start, end] with start < end, and it occupies a room from start up to, but not including, end. A room freed at time t can be reused by a meeting starting at time t. Return the minimum number of rooms needed to hold every meeting.

Example: [[9, 12], [10, 11], [11, 13], [14, 15]] gives 2. [10, 11] overlaps [9, 12], and [11, 13] reuses the room [10, 11] just freed. [[1, 5], [5, 9]] gives 1, and [] gives 0.

Constraints: up to 10^5 meetings, 0 <= start < end <= 10^6.

Counting overlaps for each meeting against all the others is O(n²) and fails the large test; aim for O(n log n).

Show hint

the answer is the largest number of meetings running at the same moment. Process meetings in start order and track when the rooms currently in use become free again.

Topic: Intervals / sweep line. Sort by start, merge; sweep events for overlaps.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc