Fewest Meeting Rooms
MediumIntervals
Problem
An office manager receives the day's meetings, each [start, end] occupying the half-open range [start, end). A room can host one meeting at a time, and a room freed at time t can host a meeting that starts at t.
Return the minimum number of rooms needed to host every meeting.
Example 1
- Input:
- meetings = [[0, 30], [5, 10], [15, 20]]
- Output:
- 2
[0, 30) needs its own room; [5, 10) and [15, 20) can share the second one.
Example 2
- Input:
- meetings = [[7, 10], [2, 4]]
- Output:
- 1
Example 3
- Input:
- meetings = [[1, 5], [5, 10]]
- Output:
- 1
The second meeting starts exactly when the first room frees up.
Constraints
- 0 ≤ meetings.length ≤ 10^5
- 0 ≤ start < end ≤ 10^9
Hint
Show the first hint
The answer is the largest number of meetings running at the same moment. When can that number change?
Walkthrough
How to approach it
01Clarify before coding
- Can a room be reused at the exact end time? Yes, ranges are half-open.
- Can the list be empty? Yes → 0 rooms.
- Do we need the room assignment or just the count? Only the count.
02Brute force
For every meeting start, count how many meetings are running at that instant; return the maximum.
Cost: O(n²) time: 10^10 checks for n = 10^5.
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.