Meeting Rooms II

 

Problem Statement: Given an array of meeting time intervals, find the minimum number of conference rooms required.

1. Clarify the problem:

  • Can we assume that the input intervals are non-overlapping?
  • Can we modify the input array?

2. Analyze the problem:

  • Input: Array of meeting time intervals
  • Output: Minimum number of conference rooms required
  • Constraints:
    • The input intervals can be overlapping.
    • The start and end times of the intervals are given as integers.

3. Design an algorithm:

  • Sort the intervals based on the start times.
  • Initialize an empty list of end times.
  • Iterate through each interval:
    • If the current interval's start time is greater than or equal to the earliest end time, update the earliest end time.
    • Otherwise, add the current interval's end time to the list of end times.
  • The length of the list of end times will be the minimum number of conference rooms required.

4. Explain your approach:

  • We will sort the intervals based on their start times to ensure that we process them in ascending order.
  • We will initialize an empty list to keep track of the end times of the meetings that are currently ongoing.
  • We will iterate through each interval and check if the current interval's start time is greater than or equal to the earliest end time. If it is, we update the earliest end time. Otherwise, we add the current interval's end time to the list of end times.
  • Finally, we return the length of the list of end times, which represents the minimum number of conference rooms required.

5. Write clean and readable code:

python
class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[0])
        end_times = [intervals[0][1]]
        
        for interval in intervals[1:]:
            if interval[0] >= end_times[0]:
                heapq.heappop(end_times)
            
            heapq.heappush(end_times, interval[1])
        
        return len(end_times)

6. Test your code: Let's test the code with some example and additional test cases:

python
# Example test case
solution = Solution()
intervals = [[0, 30], [5, 10], [15, 20]]
print(solution.minMeetingRooms(intervals))
# Expected output: 2

# Additional test cases
intervals = [[7, 10], [2, 4]]
print(solution.minMeetingRooms(intervals))
# Expected output: 1

intervals = [[0, 5], [5, 10], [10, 15]]
print(solution.minMeetingRooms(intervals))
# Expected output: 1

intervals = [[1, 5], [2, 3], [4, 6], [7, 8]]
print(solution.minMeetingRooms(intervals))
# Expected output: 3

intervals = [[1, 10], [2, 3], [4, 6], [7, 8]]
print(solution.minMeetingRooms(intervals))
# Expected output: 2

7. Optimize if necessary: The provided solution is already efficient with a time complexity of O(n log n), where n is the number of intervals. This is because we sort the intervals based on their start times. The space complexity is O(n) since we store the end times in a list.

8. Handle error cases: The code handles the case where the input intervals are empty by returning 0.

9. Discuss complexity analysis: The time complexity of the solution is O(n log n), where n is the number of intervals. This is due to the sorting operation. The space complexity is O(n) since we store the end times in a list. The solution is optimal in terms of time complexity, and there are no further optimizations possible for this problem.

Next Post Previous Post