Meeting Rooms II

MEDIUM✓ CHIP-TIMEDLC #253 — FULL STATEMENT ↗

The drill: The same booked day, but now count the minimum number of rooms needed to run every meeting without any two ever sharing a room at the same time.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

The same kind of booked day comes in again, but this time one person isn't enough — the goal is to figure out how many rooms would need to exist simultaneously to host every meeting on the list without any two sharing a room.

Meetings can overlap freely; what matters is the peak number of meetings happening at once, anywhere across the whole day, since that peak is exactly how many rooms are required.

A meeting ending at the same instant another begins doesn't need a second room for that instant — the two can pass the same room back to back. The answer is one integer: the minimum room count that covers every simultaneous meeting.

EX 01

intervals = [[1, 5], [2, 6], [8, 10]]

→ 2

TWO MEETINGS BRIEFLY OVERLAP

EX 02

intervals = [[1, 10], [2, 3], [4, 5], [6, 7]]

→ 2

ONE WIDE MEETING, SEVERAL NARROW ONES, NEVER A TRIPLE OVERLAP

EX 03

intervals = [[1, 2], [3, 4], [5, 6]]

→ 1

NO OVERLAPS AT ALL

up to a few thousand meetings per call
start and end times are non-negative integers, end never before start
meetings can overlap in any number and pattern
a meeting ending exactly when another starts doesn't need an extra room

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

At any instant, the rooms in use equal the number of meetings currently overlapping that instant. Which instant of the whole day is the busiest?

HINT 2 THE STRUCTURE

Track starts and ends as separate events on a timeline: a start adds a room in use, an end frees one. The answer is the peak simultaneous count those events reach.

HINT 3 ONE STEP FROM THE ANSWER

Sort starts and ends separately, then sweep two pointers together: whenever the next start comes before the next end, a new room is needed right now; otherwise a room frees up first. Track the running count and its maximum.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO SORTED TIMELINESPATTERN · SWEEP — STARTS VS ENDSintervals = [[1,5],[2,6],[8,10]]

STEP 1

Starts sorted [1,2,8], ends sorted [5,6,10]. Sweep both together: a start before the next end means a new room is needed right now.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/meeting-rooms-ii.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        starts = sorted(iv[0] for iv in intervals)
        ends = sorted(iv[1] for iv in intervals)

        rooms = used = i = j = 0
        n = len(intervals)
        while i < n:
            if starts[i] < ends[j]:
                used += 1
                rooms = max(rooms, used)
                i += 1
            else:
                used -= 1
                j += 1
        return rooms

TIME O(N LOG N)SPACE O(N)PYTHON · RACE PACE · 18 LN

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        peak = 0
        for start, _ in intervals:
            active = 0
            for s, e in intervals:
                if s <= start < e:
                    active += 1
            peak = max(peak, active)
        return peak

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 12 LN

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        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, used = 0, i = 0, j = 0;
        while (i < n) {
            if (starts[i] < ends[j]) {
                used++;
                rooms = Math.max(rooms, used);
                i++;
            } else {
                used--;
                j++;
            }
        }
        return rooms;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · RACE PACE · 27 LN

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int peak = 0;
        for (int[] m : intervals) {
            int active = 0;
            for (int[] iv : intervals) {
                if (iv[0] <= m[0] && m[0] < iv[1]) {
                    active++;
                }
            }
            peak = Math.max(peak, active);
        }
        return peak;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 16 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED