253.Meeting_Rooms_II(Medium).md

253. Meeting Rooms II (Medium)

Date and Time: Nov 21, 2024, 16:25 (EST)

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

Question:

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], 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

Edge Case:

Input: intervals = [[1,5],[8,9],[8,9]]

Output: 2

Constraints:

• 1 <= intervals.length <= 10^4

• 0 <= start_i < end_i <= 10^6

Walk-through:

1. First, we sort intervals.

2. We use minHeap[] to save every room's end time. Then, for every interval, we compare their end time with the current minimum end time in minHeap[0]. If start >= minHeap[0], we pop() the smallest end time room from minHeap[], and append the new end time to minHeap, otherwise, we should just append the new end time to minHeap.

Python Solution:

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # Sort intervals
        # Save the end time of each interval in minHeap, each time we process a new interval, compare the start with the top of minHeap, if the start > top of minHeap, pop the top of minHeap. Update the min number of conference rooms

        # TC: O(nlogn), SC: O(1)
        intervals.sort(key=lambda x: x[0])
        minHeap = []
        rooms = 0
        for start, end in intervals:
            # If the end from the top of minHeap expires, we pop it
            while minHeap and minHeap[0] <= start:
                heapq.heappop(minHeap)
            heapq.heappush(minHeap, end)
            rooms = max(rooms, len(minHeap))
        return rooms

Time Complexity: $O(nlogn)$
Space Complexity: $O(1)$