LeetCode 253. Meeting Rooms II

Description

https://leetcode.com/problems/meeting-rooms-ii/

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), find the minimum number of conference rooms required.

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2

Example 2:

Input: [[7,10],[2,4]]
Output: 1

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

Explanation

heap

Python Solution

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        free_rooms = []
        
        intervals = sorted(intervals, key=lambda interval: interval[0])

        heapq.heappush(free_rooms, intervals[0][1])
        
        for interval in intervals[1:]:
            if free_rooms[0] <= interval[0]:
                heapq.heappop(free_rooms)
                
            heapq.heappush(free_rooms, interval[1])
            
        
        return len(free_rooms)

• Time Complexity: ~Nlog(N)
• Space Complexity: ~N