253. Meeting Rooms II

The question sounds like scheduling, but the answer is one number: the most meetings happening at the same instant. Once you see it that way, Meeting Rooms II stops being about rooms and becomes a counting problem — a core move in the interval pattern that shows up again in sweep-line questions.

The problem

Given a list of meetings as [start, end] intervals, return the fewest conference rooms you need so no two overlapping meetings share a room. (Full statement on LeetCode.)

Take [[0, 30], [5, 10], [15, 20]]. The long [0, 30] meeting overlaps both of the others, so you need 2 rooms — even though [5, 10] and [15, 20] never touch each other and could have shared one.

Intuition: the answer is the peak concurrency

Forget assigning meetings to rooms. Ask instead: across the whole day, what is the largest number of meetings live at any single moment? That maximum is the room count, because every simultaneously-running meeting needs its own room, and no more rooms than the peak are ever occupied at once.

So the problem reduces to finding the high-water mark of overlaps. Two clean ways to compute it:

• Min-heap. Sort meetings by start time and walk them in order. Keep a heap of end times, one per room you’ve had to open. Before each new meeting, if the room that frees up earliest (the heap’s minimum end time) is already done, reuse it by popping that entry. The heap size at the end is the peak room count.
• Sweep line. Sort all start times and all end times separately, then sweep through time. Every start bumps the live count by one; every end drops it by one. The maximum the count ever reaches is the answer.

A boundary detail decides both: if a meeting ends at t and another starts at t, they can share a room (back-to-back is fine), so a start == end should count the room as freed.

Solution

The min-heap version reads closest to the intuition — the heap holds one end time per room you’ve opened, and its size tracks the running peak (it isn’t a live view of currently busy rooms, since only one expired entry is removed per meeting):

import java.util.Arrays;
import java.util.PriorityQueue;

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

        // Process meetings in the order they start.
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // Min-heap of end times, one entry per room we've opened.
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        for (int[] meeting : intervals) {
            // Free at most one room whose end time has passed, then this meeting takes a room.
            // Popping just one per meeting keeps the heap size at the running peak.
            if (!rooms.isEmpty() && rooms.peek() <= meeting[0]) {
                rooms.poll();
            }
            rooms.offer(meeting[1]);  // this meeting takes a room (new or reused)
        }
        return rooms.size();
    }
}

The sweep line drops the heap entirely. Sort starts and ends into two arrays, then advance an end pointer whenever a meeting has already finished:

import java.util.Arrays;

class Solution {
    public int minMeetingRoomsSweep(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0, end = 0;
        for (int i = 0; i < n; i++) {
            // A meeting started; if the next-to-finish one is already done, free its room.
            if (starts[i] < ends[end]) {
                rooms++;          // no room freed -> need a new one
            } else {
                end++;            // a room freed exactly in time -> reuse, don't grow
            }
        }
        return rooms;
    }
}

Both land the same count. The heap carries the actual end times of the rooms you’ve allocated (its size is the running peak); the sweep only tracks how many — it decouples the start and end streams because a room freeing up doesn’t care which meeting vacated it.

Complexity

Approach	Time	Space
Min-heap	$O(n \log n)$	$O(n)$
Sweep line	$O(n \log n)$	$O(n)$

The $\log n$ is the sort in both. The heap adds its own $O(\log n)$ per push/pop, but that’s dominated by the initial sort, so the two are the same asymptotically — the sweep just carries a smaller constant.

In an interview

Say the reframing out loud first: “the minimum rooms equals the maximum number of meetings overlapping at any instant.” That one sentence proves you understood the problem instead of pattern-matching to “heap.” Then reach for the min-heap, since it generalizes cleanly if they follow up with “which meeting goes in which room.”

The trap is the touching boundary. When one meeting ends at exactly the moment another starts, they don’t overlap — so use <= in the heap check (rooms.peek() <= meeting[0]) and < in the sweep. Flip either and you’ll over-count rooms on inputs like [[0, 10], [10, 20]]. Mention it before they ask; it’s the first edge case they’ll poke.

This is the overlap-counting sibling of Meeting Rooms, which only asks whether any two collide, and it shares the sort-first spine with Merge Intervals. The full family lives in the interval pattern hub.

References

• LeetCode 253 — Meeting Rooms II