Meeting Rooms II

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

Approach 1: Priority Queues

We can't process the given meetings in any random order. The most basic way is to process meetings in increasing order of their start times. This approach ensures that we allocate rooms to earlier meetings before later ones.

Consider the following meeting times for our example: (1, 10), (2, 7), (3, 19), (8, 12), (10, 20), (11, 30). The first value in the tuple represents the start time, and the second value represents the end time. By sorting the meetings by start time, we get:

• The first three meetings each require a new room due to overlaps.
• The next three meetings will use existing rooms. However, the last meeting will need a new room, leading to a total of 4 rooms needed.

Sorting the meetings is straightforward, but efficiently checking room availability is crucial. A naive approach would involve iterating through all rooms to find an available one for each meeting. Instead, we can use Priority Queues (or Min-Heaps) to optimize this process.

By using a Min-Heap, we keep track of room availability based on the ending times of meetings. The top element of the heap represents the room that will be free the earliest. If this room isn't available, we allocate a new room.

Algorithm

• Sort the meetings by their start time.
• Initialize a Min-Heap and add the ending time of the first meeting.
• For each subsequent meeting:
• Check if the room with the minimum ending time (top of the heap) is free.
• If free, extract the top element and add the current meeting's ending time back to the heap.
• If not free, allocate a new room and add its ending time to the heap.
• After processing all meetings, the size of the heap represents the number of rooms allocated, which is the minimum number of rooms needed.

class Solution {
   public int minMeetingRooms(int[][] intervals) {
   // Check for the base case. If there are no intervals, return 0
   if (intervals.length == 0) {
      return 0;
   }

   // Min heap
   PriorityQueue allocator =
         new PriorityQueue(
            intervals.length,
            new Comparator() {
               public int compare(Integer a, Integer b) {
               return a - b;
               }
            });

   // Sort the intervals by start time    
   Arrays.sort(
         intervals,
         new Comparator() {
         public int compare(final int[] a, final int[] b) {
            return a[0] - b[0];
         }
         });

   // Add the first meeting
   allocator.add(intervals[0][1]);

   // Iterate over remaining intervals    
   for (int i = 1; i < intervals.length; i++) {
      // If the room due to free up the earliest is free, assign that room to this meeting.
      if (intervals[i][0] >= allocator.peek()) {
         allocator.poll();
      }

      // If a new room is to be assigned, then also we add to the heap,    
      // If an old room is allocated, then also we have to add to the heap with updated end time.
      allocator.add(intervals[i][1]);
   }

   // The size of the heap tells us the minimum rooms required for all the meetings.
   return allocator.size();
   }
}
            

Complexity Analysis

Time Complexity: O(N log N)
The time complexity consists of two parts:

• Sorting the meetings, which takes O(N log N), where N is the number of meetings.
• Managing the Min-Heap, which involves N add operations and up to N extract-min operations. Each heap operation takes O(log N), resulting in an overall time complexity of O(N log N).

Space Complexity: O(N)
The space complexity is determined by the Min-Heap, which can contain up to N elements in the worst case, leading to a space complexity of O(N).