Minimum Meeting Rooms

Hard · rating 1600 · sorting, greedy

The first line contains n. Each of the next n lines has the start and end time of a meeting. Print the minimum number of rooms needed so that no two overlapping meetings share a room (a meeting occupies [start, end)).

Constraints: 1 ≤ n ≤ 10⁵

Editorial

Minimum Meeting Rooms is a classic interval-scheduling interview problem: given meeting start and end times, find the greatest number that overlap at once — that's how many rooms you need.

Approach (chronological sweep)

Sort start times and end times separately. Sweep through the starts; before each meeting begins, free every room whose meeting has already ended. The running count of busy rooms peaks at the answer.

starts.sort(); ends.sort()
rooms = peak = j = 0
for s in starts:
    while ends[j] <= s:
        j += 1; rooms -= 1
    rooms += 1
    peak = max(peak, rooms)
return peak

Complexity

Time: O(n log n). Space: O(n).

Open Minimum Meeting Rooms in Code Arena →