Question/Understanding

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

#Constraints:
1 <= intervals.length <= 104
0 <= starti < endi <= 106

#Given Testcases:
Example 1
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2
Input: intervals = [[7,10],[2,4]]
Output: 1

Example 3
Input: intervals = [[1,5],[8,9],[8,9]]
Output: 2

Example 4
Input: intervals = [[9,10],[4,9],[4,17]]
Output: 2

Matching

This problem can be solved using nested loop and arrays only but using Min-Heap will be efficient.

Plan

It will be a good idea to sort the intervals in ascending order so that we can see the collisions easily. For example, for Example 1, it makes sense to allocate two different rooms to colliding meetings: [0,30] and [5,10].

Now, in order to make sure we use minimum rooms, we need to come up with an approach to see if a previously occupied room is now available. One approach is to iterate over all the rooms and see if one of them is available. However, a better approach is to use a Min-heap data structure. We can store the meeting ending time in the min-heap. This allows us to peek at the meeting that is going to end the soonest, and if it's going to end earlier than the new meeting, we can allocate the room to the new meeting. Referring back to Example 1, the room used by [5, 10] can be allocated to [15,20] as 10 ends before 15 starts. Similarly, a room can be allocated to two meetings with same ending and starting time. For example: [4, 9] and [9, 12]. It is to be noted that it is necessary to declare the room is available before allocating it to a new meeting. At the end, we will simply return the length of our min-heap data structure.

Implement

import heapq
class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        rooms = []
        heapq.heappush(rooms, intervals[0][1])
        for i in intervals[1:]:
            if rooms[0]<= i[0]:
                heapq.heappop(rooms)
            heapq.heappush(rooms, i[1])
        return len(rooms)

Review and Evaluate

Time Complexity: Sorting the intervals will take O(Nlog(N)) time and as any min-heap operation takes O(log(N)), for N operations, it takes O(Nlog(N)) time. Overall, the time complexity is O(Nlog(N)).

Space Complexity: The min-heap takes O(N) space.