Meeting Rooms II
MediumChronological sweep · peak overlap = rooms
The most meetings happening at the same time is how many rooms you need.
The idea
Separate and sort all start and end times. Sweep in time order: a start needs a room (+1), an end frees one (−1). The highest simultaneous count is the number of rooms.
s
0
5
15
0
1
2
Step 1 of 5. Sort starts [0,5,15] and ends [10,20,30]. Sweep: a start needs a room, an end frees one. Values: 0, 5, 15. Pointers: s at index 0.
1/5
Optimal
timeO(n log n)spaceO(n)
Track concurrent meetings.
1starts.sort(); ends.sort();2let rooms = 0, best = 0, e = 0;3for (let s = 0; s < n; s++) {4 if (starts[s] < ends[e]) rooms++;5 else e++, rooms; // a meeting ended6 best = Math.max(best, ++/*balance*/ rooms - 1);7}Input
- array
- [0, 5, 15]
Memory
- s
- = 0 [0]
- e
- —
- rooms
- —
Output
- peak
- —
- rooms needed
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- intervals = [[0,30],[5,10],[15,20]]
- Output:
- 2
- Explanation:
- At the busiest moment, 2 rooms are needed.
Example 2
- Input:
- intervals = [[7,10],[2,4]]
- Output:
- 1
- Explanation:
- No overlap → 1 room.
Example 3
- Input:
- intervals = [[1,5],[2,6],[3,7]]
- Output:
- 3
- Explanation:
- All three overlap → 3.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.