Problem 15.4 · IntervalsMedium

Meeting Rooms II

PatternMerge Intervals Top K with a Heap

What it teaches: The maximum number of simultaneous intervals, with a min-heap of end times (or a sweep line).

Practise it on judges as “Meeting Rooms II”.

The problem

Return the minimum number of rooms needed to hold all meetings. A meeting ending at t frees its room for one starting at t.

Example 1

Input: [[0,30],[5,10],[15,20]]
Output: 2

Example 2

Input: [[7,10],[2,4]]
Output: 1

Constraints

1 ≤ n ≤ 10⁴

Pattern clues in the wording

→ Maximum overlap at any moment
→ Reuse a room once its meeting ends

These clues point to Merge Intervals: Sort intervals by start; each one either overlaps the last merged interval (extend it) or starts a new one.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	intervals = [[0,30],[5,10],[15,20]]	2
2	intervals = [[7,10],[2,4]]	1

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Min-heap of end times · O(n log n)2. Sweep line over sorted starts and ends · O(n log n)

Min-heap of end times

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

Sort by start. For each meeting, if the earliest-ending room is free (end ≤ start), reuse it (poll). Push this meeting's end. The heap's maximum size is the answer.

▶ Dry run: Rooms as a heap of end times[[0,30],[5,10],[15,20]]

0-30

5-10

15-20

room end times (min-heap)(list)

Step 1/3Meeting 0–30 takes room 1.

Approach 1

import java.util.*;

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

Verdict: Clear and standard.

Sweep line over sorted starts and ends

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

Sort starts and ends separately. For each start, release rooms whose end ≤ this start, then take one. Track the maximum.

Approach 2

import java.util.Arrays;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] s = new int[n], e = new int[n];
        for (int i = 0; i < n; i++) { s[i] = intervals[i][0]; e[i] = intervals[i][1]; }
        Arrays.sort(s);
        Arrays.sort(e);
        int rooms = 0, best = 0, j = 0;
        for (int start : s) {
            while (e[j] <= start) { rooms--; j++; }
            rooms++;
            best = Math.max(best, rooms);
        }
        return best;
    }
}

Verdict: No heap; same complexity.

Before you submit

Edge cases and common mistakes

Test these inputs

Back-to-back meetings
All meetings at the same time
One meeting

Mistakes people make

Polling more than one room per meeting in the heap version (the heap size should equal rooms in use).
Treating back-to-back meetings as overlapping.

Interview

Follow-up questions

How would you also assign room numbers?

Command Palette