194. Meeting Rooms II

Sort meetings by start time, then use a min-heap to track the earliest ending meeting. If the next meeting starts after the earliest ending one, reuse that room; otherwise allocate a new room.

Approach

1. Sort intervals by start time.
2. Use a min-heap to track end times of ongoing meetings.
3. For each meeting, if its start >= heap top (earliest end), pop that room.
4. Push the current meeting's end time onto the heap.
5. The heap size at the end is the number of rooms needed.

Walk-through

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

• Sort → same order.
• [0,30]: heap = [30], rooms = 1.
• [5,10]: 5 < 30, can't reuse → heap = [10,30], rooms = 2.
• [15,20]: 15 >= 10, reuse → pop 10, push 20 → heap = [20,30], rooms = 2.

Answer: 2.

Complexity

• Time: O(n log n) for sorting + heap operations.
• Space: O(n) for the heap.

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