Meeting Rooms II

medium heap intervals

Problem

Given an array of meeting time intervals [start, end), return the minimum number of conference rooms required so every meeting has a room.

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();
}

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