Meeting Rooms II

• How many meeting rooms are required?

Approach/give_gyan

• First sort the intervals based on the starting time of meeting.
• Ininitialization_phase create Heap, Heap by default is Min heap and push the ending time of first meeting.
• maintaince_phase the loop should start from second interval as first interval is already pushed.
• python_trick for Python Slicing can be used for loop, for i in intervals[1:], intervals from 1 to all.
• python_trick useheapq module, which takes array as first argument and value to be processed as second argument.heapq has heappush and heappop methods.
• If the first meeting ending time is less than second meeting starting time then no additional meeting room is required and this pop the element from heap.
• Always push the ending time of next meeting.
• Intermination_phase return the length of the heap.

Code

# Time: O(nlogn)
# Space: O(n)
from heapq import heappush, heappop
 
 
class Solution(object):
    def minMeetingRooms(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[0])
        free_rooms = []
        
        heappush(free_rooms, intervals[0][1])
        for interval in intervals[1:]:
            if free_rooms[0] <= interval[0]:
                heappop(free_rooms)
            
            heappush(free_rooms, interval[1])
        
        return len(free_rooms)