Given an array of meeting time intervals
intervals[i] = [starti, endi], return the minimum number of conference rooms required.
Input: intervals = [[0,30],[5,10],[15,20]] Output: 2
Input: intervals = [[7,10],[2,4]] Output: 1
1 <= intervals.length <= 104
0 <= starti < endi <= 106
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.
class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int: meetings =  intervals = sorted(intervals, key=lambda interval:interval) heapq.heappush(meetings, intervals) for interval in intervals[1:]: if interval >= meetings: heapq.heappop(meetings) heapq.heappush(meetings, interval) else: heapq.heappush(meetings, interval) return len(meetings)
- Time Complexity: ~Nlog(N)
- Space Complexity: ~N