Meeting Rooms II

Problem: Meeting Rooms

We can use push all intervals into a heap based on its start time. When we do extract-min on the heap, we can get an activity starts first, and arrange a room for it. Then we fetch the 2nd interval and see whether it interferes with existing rooms. If so, we arrange a new room for it. If not, we just add it to existing rooms.

To prove we will get the minimum number of rooms, we can see that no intervals in any room can be merged into other rooms.

Code in Python:

import heapq

class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        intervals.sort(key=lambda x:x.start)
        heap = []  # stores the end time of intervals
        for i in intervals:
            if heap and i.start >= heap[0]: 
                # means two intervals can use the same room
                heapq.heapreplace(heap, i.end)
            else:
                # a new room is allocated
                heapq.heappush(heap, i.end)
        return len(heap)