Meeting Rooms Iii - Leetcode Solution

Problem statement:

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

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

Solution:

The problem can be solved by arranging the meeting intervals in ascending order of their start time. We can then use a min heap to keep track of the end times of the meetings that are currently happening. For each new meeting interval, we can compare its start time with the end time of the earliest (smallest) end time meeting in the min heap. If the start time of the new meeting is greater than the end time of the earliest meeting, we can replace the earliest meeting with the new meeting, as the earlier meeting has already ended. If the start time of the new meeting is less than or equal to the end time of the earliest meeting, then we need to allocate another room for the new meeting.

The number of meeting rooms required will be the size of the min heap at the end of all the iterations.

Here is the detailed step-by-step solution:

1. Sort the meeting intervals in ascending order of their start times.

2. Create a min heap to keep track of the end times of the meetings that are currently happening. Add the end time of the first meeting to the min heap.

3. Iterate through the remaining meeting intervals. For each meeting interval, compare its start time with the end time of the earliest (smallest) end time meeting in the min heap.

4. If the start time of the new meeting is greater than the end time of the earliest meeting, we can replace the earliest meeting with the new meeting, as the earlier meeting has already ended. Update the end time of the earliest meeting in the min heap to be the end time of the new meeting.

5. If the start time of the new meeting is less than or equal to the end time of the earliest meeting, then we need to allocate another room for the new meeting. Add the end time of the new meeting to the min heap.

6. The number of meeting rooms required will be the size of the min heap at the end of all the iterations.

Here is the Python code implementation:

import heapq

class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int:

    # Sort the meeting intervals in ascending order of their start times
    intervals.sort(key = lambda x: x[0])
    
    # Create a min heap to keep track of the end times of the meetings that are currently happening
    min_heap = []
    
    # Add the end time of the first meeting to the min heap
    heapq.heappush(min_heap, intervals[0][1])
    
    # Iterate through the remaining meeting intervals
    for i in range(1, len(intervals)):
        
        # Compare the start time of the new meeting with the end time of the earliest meeting in the min heap
        if intervals[i][0] >= min_heap[0]:
            
            # Replace the earliest meeting with the new meeting, as the earlier meeting has already ended
            heapq.heappop(min_heap)
        
        # Add the end time of the new meeting to the min heap
        heapq.heappush(min_heap, intervals[i][1])
    
    # The number of meeting rooms required will be the size of the min heap at the end of all the iterations
    return len(min_heap)

Time Complexity: The time complexity of this solution is O(nlogn), where n is the number of meeting intervals. The sorting takes O(nlogn) time and the min heap operations take O(nlogn) time.

Space Complexity: The space complexity is O(n), as we need to store the meeting intervals in a list and the min heap can have at most n elements.

1