LeetCode #253: Meeting Rooms II

LeetCode Solutions

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

To solve this problem, we will use a heap and a greedy approach. We will keep track of the end time of each meeting that has already been scheduled. We will start by scheduling the first meeting and adding its end time to our heap. We will then iterate through the rest of the meetings and check if their start time is after or equal to the end time of the earliest ending meeting in our heap. If it is, we can remove that meeting from the heap and add the end time of the new meeting to the heap. If it is not, we need to schedule another meeting room and add its end time to the heap.

  1. If there are no meetings, return 0.
  2. Sort the meetings in increasing order of their start times.
  3. Create a heap and add the end time of the first meeting to it.
  4. Iterate through the rest of the meetings:
    • If the start time of the current meeting is after or equal to the end time of the earliest ending meeting in our heap, remove that meeting from the heap and add the end time of the current meeting to the heap.
    • If the start time of the current meeting is before the end time of the earliest ending meeting in our heap, we need to schedule another meeting room. Add the end time of the current meeting to the heap.
  5. Return the size of the heap.

Here is the Python code that implements the above approach:

import heapq
from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        intervals = sorted(intervals, key=lambda x: x[0])
        free_rooms = []
        heapq.heappush(free_rooms, intervals[0][1])
        for meeting in intervals[1:]:
            if free_rooms[0] <= meeting[0]:
                heapq.heappop(free_rooms)
            heapq.heappush(free_rooms, meeting[1])
        return len(free_rooms)

Time and Space Complexity

The time complexity of this solution is O(N log N), where N is the number of meetings. We have to sort the meetings in the beginning, which takes O(N log N) time. Then, for each meeting, we do one push and at most one pop from the heap, which takes O(log N) time. Thus, the overall time complexity is O(N log N).

The space complexity of this solution is O(N), since we need to store the end times of all the meetings in the heap.