134.Meeting Rooms II

MediumBlind 75Intervals · 5/6

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that every meeting can take place.

A room freed at time t can immediately host a meeting starting at t: [5,10] and [10,15] can share one room.

Examples

Input:  intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: [0,30] needs its own room; [5,10] and [15,20] can share the second room.

Input:  intervals = [[7,10],[2,4]]
Output: 1
Explanation: The meetings don't overlap.

Input:  intervals = [[1,5],[2,6],[3,7],[5,8]]
Output: 3
Explanation: At time 3, meetings [1,5], [2,6], [3,7] all run. [5,8] reuses the room freed at 5.

Constraints

1 <= intervals.length <= 10^4
0 <= start_i < end_i <= 10^6

💡 Key Insight

The answer is the maximum number of meetings running at the same moment. Process meetings in start order and track when currently occupied rooms free up: if the earliest-ending room is free by the time the next meeting starts, reuse it; otherwise open a new room. A min-heap of end times does this directly — and since only counts matter, two sorted arrays of starts and ends with two pointers do it with even less overhead.

Brute Force (Count Overlaps at Each Start)

TimeO(n²)SpaceO(1).

Intuition

The number of simultaneous meetings only increases at a start time, so the peak occurs at some meeting's start. For each start s, count how many meetings are active at s (start <= s < end). The largest count is the answer.

Algorithm

For each meeting i, let s = intervals[i][0].
Count meetings j with intervals[j][0] <= s < intervals[j][1].
Track the maximum count and return it.

Visualization

[[0,30],[5,10],[15,20]]
s = 0:  active [0,30]                 -> 1
s = 5:  active [0,30], [5,10]         -> 2
s = 15: active [0,30], [15,20]        -> 2   ([5,10] ended at 10)
max = 2

Code

java

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int best = 0;
        for (int[] cur : intervals) {
            int s = cur[0];
            int active = 0;
            for (int[] other : intervals) {
                if (other[0] <= s && s < other[1]) { // other is running at time s
                    active++;
                }
            }
            best = Math.max(best, active);
        }
        return best;
    }
}

Complexity

Time: O(n²) — n start times, each checked against all n meetings.
Space: O(1).

Min-Heap of End Times

TimeO(n log n)SpaceO(n)

Intuition

Sort meetings by start. A min-heap stores the end time of every occupied room; its root is the room that frees up first. For each meeting, if that earliest end is <= start, the room is free — remove its old end time. Then push the new meeting's end. The heap size at the end is the number of rooms ever needed simultaneously.

Algorithm

Sort intervals by start.
For each meeting: if heap is non-empty and heap.peek() <= start, poll() (reuse that room).
offer(end).
Return heap.size().

Visualization

[[1,5],[2,6],[3,7],[5,8]] (already sorted):

flowchart TD
    A["[1,5]: heap empty<br/>push 5 -> {5}"] --> B["[2,6]: 5 <= 2? no<br/>push 6 -> {5,6}"]
    B --> C["[3,7]: 5 <= 3? no<br/>push 7 -> {5,6,7}"]
    C --> D["[5,8]: 5 <= 5? yes, poll 5<br/>push 8 -> {6,7,8}"]
    D --> E["heap size = 3 rooms"]

Code

java

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

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> ends = new PriorityQueue<>(); // end times of busy rooms
        for (int[] m : intervals) {
            if (!ends.isEmpty() && ends.peek() <= m[0]) {
                ends.poll(); // earliest room is free: reuse it
            }
            ends.offer(m[1]);
        }
        return ends.size();
    }
}

Complexity

Time: O(n log n) — sorting plus n heap operations.
Space: O(n) — the heap in the worst case (all meetings overlap).

Two Pointers on Sorted Starts and EndsOptimal

TimeO(n log n)SpaceO(n)

Intuition

Which meeting ends doesn't matter — only when rooms free up. Sort all start times and all end times separately. Walk the starts in order; pointer e marks the earliest end not yet "used". If the current start is >= ends[e], some meeting finished, so its room is reused (e++); otherwise we need a new room.

Algorithm

Build sorted arrays starts and ends.
rooms = 0, e = 0.
For each i: if starts[i] >= ends[e], e++ (reuse); else rooms++.
Return rooms.

Dry Run

starts = [1, 2, 3, 5]
ends   = [5, 6, 7, 8]

i=0 start 1 >= ends[0]=5? no  -> rooms = 1
i=1 start 2 >= 5? no          -> rooms = 2
i=2 start 3 >= 5? no          -> rooms = 3
i=3 start 5 >= 5? yes         -> reuse, e = 1 (rooms stays 3)
answer 3

sequenceDiagram
    participant S as starts
    participant R as rooms
    participant E as ends pointer
    S->>R: 1 starts, no room free, rooms = 1
    S->>R: 2 starts, rooms = 2
    S->>R: 3 starts, rooms = 3
    E->>R: meeting ending at 5 frees a room
    S->>R: 5 starts, reuses it, rooms stays 3

Code

java

import java.util.Arrays;

class Solution {
    public int minMeetingRooms(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;
        int e = 0; // earliest end time not yet matched to a reuse
        for (int i = 0; i < n; i++) {
            if (starts[i] >= ends[e]) {
                e++; // a meeting has ended: take over its room
            } else {
                rooms++; // everyone is still busy: open a new room
            }
        }
        return rooms;
    }
}

Complexity

Time: O(n log n) — two primitive sorts; the scan is O(n).
Space: O(n) — the two arrays.

Complexity Comparison

Approach	Time	Space
Count Overlaps at Each Start	O(n²)	O(1)
Min-Heap of End Times	O(n log n)	O(n)
Two Pointers (Starts / Ends)	O(n log n)	O(n)

Common Pitfalls

Using < instead of <= when checking whether a room is free — a meeting ending at 10 frees its room for one starting at 10.
Forgetting to sort by start before using the heap — processing out of order gives wrong reuse decisions.
Returning the number of polls or the final rooms counter from the wrong branch; with the heap, the answer is its final size.
Thinking the two-pointer method loses track of which meeting is in which room — it doesn't need to; only the counts of starts and ends before each moment matter.