Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Example 1:
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Example 2:
Input: intervals = [[7,10],[2,4]] Output: 1
Constraints:
1 <= intervals.length <= 10^40 <= starti < endi <= 10^6
The description was taken from https://leetcode.com/problems/meeting-rooms-ii/.
#O(N(log N)) Time, O(N) Spaceclass Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: if not intervals: return 0 heap = [] intervals.sort(key= lambda times: times[0]) heapq.heappush(heap, intervals[0][1]) for meeting in intervals[1::]: if heap[0] <= meeting[0]: heapq.heappop(heap) heapq.heappush(heap, meeting[1]) return len(heap)This problem could actually be practical in a real-world scenario.
Let's picture that we have an administrative role and we came into work early to reserve a bunch of meeting rooms for today's meetings.
What we can do is sort the intervals meetings by start times, then sort any meetings we would need to allocate by end times through the use of a heap. We can then cross-reference any reusable meeting rooms by seeing if the first meeting room from the heap has ended before any current iteration's meeting has started. If that is the case, then we can reuse a meeting. If not, we need to allocate a new meeting. By doing this, we can allocate only as many rooms as we need so the other administrators don't get upset.
A hint that using a heap is the way to go is when we need to think of inserting and retrieving information into a sorted data structure.
First off, if the intervals array we have gotten is empty, then we have no meetings and don't need any meeting rooms.
if not intervals: return 0
Otherwise, we will start by initializing our meeting rooms heap.
The size of this heap will be the answer to our question once we're finished.
heap = []
Next, we will sort the intervals by the start time.
We want to be able to iterate through this array and compare each meeting's start time with the heap's meeting end times, so it makes sense that we have this linear time relationship by sorting the interval start times. This way, we don't have to travel through time to allocate new rooms.
intervals.sort(key= lambda times: times[0])
If we have at least one meeting, then we know we need at least one room.
If this is the case, we should give the first room to the first meeting.
We will push the meeting's end time onto the heap.
heapq.heappush(heap, intervals[0][1])
This is like if we reserved the meeting and wrote on the door, "This meeting will be over at intervals[0][1] O'clock.".
For the remainder of the meetings, we will play it by ear.
for meeting in intervals[1::]:
We will compare the first meeting room within our heap's end time to our current meeting start time. Remember, the heap is sorting the rooms by end times, so if the first meeting hasn't ended then neither have the rest.
If the first meeting has ended before or during our current meeting starts, we will just pop that room off the heap and it's ours!
if heap[0] <= meeting[0]: heapq.heappop(heap)
Whether we just grabbed the vacant meeting room, or we needed to reserve a new meeting room, we will still need to note what time the meeting will end so future coworkers can grab vacant rooms after each meeting ends.
heapq.heappush(heap, meeting[1])
At the end of our traversal of the intervals, the heap, that is, the list of ongoing meeting end-times will be the minimum number of conference rooms required to fulfill all of the meeting times we would need.
return len(heap)