Fewest Conference Rooms
MediumHeap / Priority Queue
Problem
An office receives meetings, where meetings[i] = [start, end] is a meeting that occupies a room from time start up to, but not including, time end. A meeting ending at time t frees its room for a meeting starting at t.
Return the minimum number of rooms needed so that every meeting gets a room for its whole duration.
Example 1
- Input:
- meetings = [[9, 12], [10, 11], [11, 13], [14, 15]]
- Output:
- 2
[9,12] and [10,11] overlap. [11,13] reuses the room freed by [10,11]. [14,15] reuses any room.
Example 2
- Input:
- meetings = [[1, 5], [5, 8]]
- Output:
- 1
The first ends exactly when the second starts.
Constraints
- 1 ≤ meetings.length ≤ 10^5
- 0 ≤ start < end ≤ 10^9
Hint
Show the first hint
Handle meetings in order of start time. When a new meeting starts, which existing room is the best candidate to reuse?
Walkthrough
How to approach it
01Clarify before coding
- Are intervals half-open? Yes: [1, 5] and [5, 8] can share a room.
- Do I need the assignment or just the count? Just the count.
- Is the input sorted? No.
02Brute force
For each meeting, count how many meetings are running at its start time; the maximum over all starts is the answer.
Cost: O(n²): 10^10 comparisons for 10^5 meetings.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.