Meeting Rooms II

medium heap intervals

Problem

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Inputintervals = [[0,30],[5,10],[15,20]]

Output2

Sort by start. Min-heap holds end times of in-progress meetings; if the soonest end ≤ current start, reuse that room.

intervals (e.g. "0,30; 5,10; 15,20")

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda iv: iv[0])
    heap = []
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
    return len(heap)

function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = [];  // min-heap of end times
  for (const [start, end] of intervals) {
    if (heap.length && heap[0] <= start) heapPop(heap);
    heapPush(heap, end);
  }
  return heap.length;
}
// (heapPush / heapPop are standard binary-heap helpers)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int[] iv : intervals) {
            if (!heap.isEmpty() && heap.peek() <= iv[0]) heap.poll();
            heap.offer(iv[1]);
        }
        return heap.size();
    }
}

int minMeetingRooms(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> heap;
    for (auto& iv : intervals) {
        if (!heap.empty() && heap.top() <= iv[0]) heap.pop();
        heap.push(iv[1]);
    }
    return heap.size();
}

Explanation

We want the fewest rooms so no two overlapping meetings share one. The idea: process meetings in order of start time and use a min-heap of end times to track which rooms are busy.

The heap's root is the meeting that finishes soonest. When a new meeting starts, we check that root: if the earliest-finishing meeting has already ended by the new start time (heap[0] <= start), that room is free, so we pop it and reuse the room.

Either way we then push the new meeting's end time. The number of rooms used at any moment is just the size of the heap, and since we only ever add when no room is free, the final heap size is the maximum overlap — the answer.

Example: intervals=[[0,30],[5,10],[15,20]]. Sorted by start, we place [0,30) (heap=[30]). [5,10) starts at 5 but the soonest end is 30 > 5, so we need a second room (heap=[10,30]). [15,20) starts at 15 and 10 ≤ 15, so we reuse that room (heap=[20,30]).

The heap never grows beyond 2, so the answer is 2 rooms.

Time: O(n log n) Space: O(n)