LeetCode 253. Meeting Rooms II

Description

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

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 <= 104
• 0 <= starti < endi <= 106

Explanation

First, sort the meetings by their starting time. Then iterate the meeting list and have a list to track the ongoing meetings ordering by ended time, if the meeting start time is greater than the first ongoing meeting ending time, remove the first meeting and append the meeting. If the meeting start time is less than the first ongoing meeting ending time, append the meeting. We can use a heap to help maintain the ongoing meeting orders.

Python Solution

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        meetings = []
                
        intervals = sorted(intervals, key=lambda interval:interval[0])
        
        heapq.heappush(meetings, intervals[0][1])

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

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