Code Implementation

import heapq

class Solution:
    def minMeetingRooms(self, intervals):
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[0])
        heap = []

        heapq.heappush(heap, intervals[0][1])

        for interval in intervals[1:]:
            if interval[0] >= heap[0]:
                heapq.heappop(heap)
            heapq.heappush(heap, interval[1])

        return len(heap)
      

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> heap;
        heap.push(intervals[0][1]);

        for (int i = 1; i < intervals.size(); ++i) {
            if (intervals[i][0] >= heap.top()) {
                heap.pop();
            }
            heap.push(intervals[i][1]);
        }
        return heap.size();
    }
};
      

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        heap.add(intervals[0][1]);

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= heap.peek()) {
                heap.poll();
            }
            heap.add(intervals[i][1]);
        }
        return heap.size();
    }
}
      

var minMeetingRooms = function(intervals) {
    if (intervals.length === 0) return 0;

    intervals.sort((a, b) => a[0] - b[0]);
    let heap = [];

    const addRoom = (end) => {
        heap.push(end);
        heap.sort((a, b) => a - b);
    };

    addRoom(intervals[0][1]);

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= heap[0]) {
            heap.shift();
        }
        addRoom(intervals[i][1]);
    }
    return heap.length;
};
      

Problem Description

You are given an array of meeting time intervals, where each interval is represented as a pair [start, end]. Your task is to determine the minimum number of conference rooms required so that all meetings can take place without any overlaps.

• Each meeting has a start and end time.
• No two meetings can be held in the same room at the same time.
• Return the minimum number of rooms needed to accommodate all meetings.

Example: If the input is [[0, 30], [5, 10], [15, 20]], you should return 2 because at most two meetings overlap at any point in time.

Thought Process

The first instinct might be to check each meeting against every other meeting to see if they overlap, assigning rooms as needed. While this works for small inputs, it quickly becomes inefficient (brute-force).

To optimize, we can shift perspective: instead of focusing on assigning rooms directly, let's track when rooms become free. If a meeting starts after another ends, it can reuse the same room. Thus, we need a way to efficiently keep track of the earliest ending meetings.

This leads us to use a min-heap (priority queue) to always know which room will be free next. By sorting meetings by start time and always checking the soonest available room, we ensure we use the minimum number of rooms.

Solution Approach

• Step 1: Sort the intervals.
  Sort all meetings by their start times. This ensures we process them in chronological order.
• Step 2: Use a min-heap to track end times.
  The heap will always contain the end times of meetings currently using a room. The smallest end time is always at the top.
• Step 3: Iterate through meetings.
  For each meeting:
  • If the meeting's start time is after or equal to the earliest end time (top of the heap), that room is now free. Remove it from the heap.
  • Add the current meeting's end time to the heap (since this room is now occupied).
• Step 4: The answer is the heap size.
  After processing all meetings, the number of rooms needed is the maximum size the heap reached, which is the number of concurrent meetings at any time.

Using a heap lets us efficiently find and release rooms as soon as they become available, ensuring we never use more rooms than necessary.

Example Walkthrough

Let's use the input [[0, 30], [5, 10], [15, 20]]:

1. Sort intervals:
   Already sorted: [[0, 30], [5, 10], [15, 20]]
2. Initialize heap with first meeting's end:
   Heap: [30]
3. Second meeting [5, 10]:
   Start time 5 < 30 (heap top), so need a new room.
   Heap: [10, 30]
4. Third meeting [15, 20]:
   Start time 15 >= 10 (heap top), so room with end time 10 is now free.
   Pop 10, add 20.
   Heap: [20, 30]
5. Result:
   Heap size is 2, so 2 rooms are needed.

This demonstrates how the heap always tracks the rooms currently in use and allows us to reuse rooms optimally.

Time and Space Complexity

• Brute-force approach:
  For each meeting, check all others for overlap and assign rooms. This is O(n^2) time and O(n) space.
• Optimized heap approach:
  
  • Sorting intervals: O(n \log n)
  • Each meeting is pushed/popped from the heap at most once: O(n \log n)
  • Total time: O(n \log n)
  • Space: The heap stores at most n end times, so O(n) space.

The heap-based solution is much more efficient, especially for large inputs.

Summary

The key insight is to treat the problem as one of efficiently tracking room availability, not just overlaps. By sorting meetings and using a min-heap to always know which room becomes free next, we can assign rooms optimally. This approach is both elegant and efficient, leveraging simple data structures to solve a classic scheduling problem.