Given meeting start and end times, find the minimum number of rooms needed. Meetings that overlap need different rooms.
DSA Animator › DSA Revision › Intervals › Meeting Rooms II
Remember: the heap top is the room that frees up first. The heap size is the number of rooms in use. The video solves Meeting Rooms II (LeetCode 253, Medium) with the Min Heap of End Times pattern from the Intervals topic, and you can replay every step in the interactive Meeting Rooms II animation.
Given meeting start and end times, find the minimum number of rooms needed. Meetings that overlap need different rooms.
For meetings 0 to 30, 5 to 10 and 15 to 20, the answer is 2 rooms.
Checking every time point and counting overlaps is slow. We only need to know which room frees up first.
Sort the meetings by start time. Keep a min heap of end times, one per room in use. If the earliest end is not after the new start, reuse that room, otherwise open a new one.
0 to 30 opens room 1, and the heap holds 30. 5 to 10 starts before 30, so open room 2, and the heap holds 10 and 30. 15 to 20 starts after 10, so it reuses that room, and the heap holds 20 and 30. The heap size, 2, is the number of rooms.
In code, sort by start. For each meeting, if the heap top is at most the start, poll it. Then offer the meeting end, and return the heap size. It's O of n log n time and O of n space.
Remember: the heap top is the room that frees up first. The heap size is the number of rooms in use.