Difficulty: MediumIntervals

Meeting Rooms II

Problem in Plain English

You are given a list of meeting time intervals and must find the smallest number of rooms so that overlapping meetings never share one. Return that minimum room count.

Problem Statement

Given a nonempty list intervals of meetings [start, end], return the minimum number of rooms needed to host them without conflicts. Each meeting has positive duration. A room is free at its meeting end, so a meeting starting at the same instant may reuse it; occupancy is the half-open interval from start inclusive to end exclusive. Input order is arbitrary.

The implementations below preserve the input order and row values. Only the room count is returned, not a schedule.

Constraints

$1 \leq n = \mathrm{intervals.length} \leq 10^4$ .
Every interval contains exactly two integer endpoints.
$0 \leq \mathrm{start}_i < \mathrm{end}_i \leq 10^6$ .

Examples

Example 1

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

The long meeting overlaps each shorter one. The shorter meetings do not overlap each other, so they share a second room.

Example 2

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

Sorting reveals that [2,4] finishes before [7,10] begins. One room suffices even though the input is unsorted.

Example 3

Input: intervals = [[1,5],[5,10]]
Output: 1

At time 5 the first meeting releases its room before the second begins. Equal end and start times do not overlap.

Example 4

Input: intervals = [[2,8],[2,8],[2,8]]
Output: 3

All three meetings are active together from time 2 until time 8; duplicate meetings still need distinct rooms.

Example 5

Input: intervals = [[0,1000000]]
Output: 1

A single positive-duration meeting needs one room regardless of its length.

Intuition

The required rooms equal the largest number of meetings active at the same instant. In Example 1, [0,30] overlaps [5,10], forcing two rooms, but its second room becomes free before [15,20] starts. Unlike closed-interval merging, a meeting occupies a room from its start up to but excluding its end. Thus a meeting ending at 5 and another starting at 5 may share one room. We can simulate actual rooms or count starts and ends without assigning room identities.

Approaches

Room List Scan

Solution Details

Reveal Room List Scan: intuition, complexity, and code

Intuition

Processing meetings in start order and seating each one in the first room that has freed up directly simulates room reuse. The slowdown is the linear scan of every allocated room for each new meeting.

Step-by-Step Logic

Sort a new outer copy of the meetings by start and create an empty list of room end times. Example 1 keeps order [[0,30],[5,10],[15,20]].
For each meeting scan allocated rooms. Reuse the first room whose end is at most the new start, replacing that room end with the new meeting end.
If every room is still busy, append a new room. Example 1 allocates ends 30 and 10 for the first two meetings.
Continue until all meetings are seated, then return the number allocated. Example 1 scans ends 30 and 10 for start 15, reuses the second room and changes its end to 20; return 2.

Why It Works

Processing starts in sorted order ensures every room end describes the last assigned meeting in that room. Reusing a room only when its end is at most the next start creates no conflict, and choosing any free room is safe because its past meetings are already finished. If no allocated room is free at a start time, every one is occupied and the arriving meeting forces one additional room: the simultaneous occupancy proves that many rooms are unavoidable. Every increase in the allocated count is therefore justified by a lower bound, while the constructed assignment uses exactly that count. The final count is consequently minimal. Sorting an outer copy and modifying only room-end scalars preserves the input.

Dry Run

Room List Scan: variable states at each step
meeting	rooms before	inspected room ends	action	rooms after	count
initialize	`[]`	none	sort outer copy	`[]`	`0`
`[0,30]`	`[]`	none	allocate	`[30]`	`1`
`[5,10]`	`[30]`	`30`: `5 >= 30` false	allocate	`[30,10]`	`2`
`[15,20]`	`[30,10]`	`30`: false; `10`: `15 >= 10` true	reuse room index `1`	`[30,20]`	`2`
finish	`[30,20]`	none	return allocated count	unchanged	return `2`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Sorting an outer copy costs O(n log n). Each meeting may then scan every allocated room; n identical overlapping meetings perform n(n - 1)/2 failed room checks, so the quadratic scan dominates. The outer copy, up to n room-end scalars and sorting workspace use O(n) auxiliary space; row references are read-only and the returned count is constant-size.

Code

Solution.java

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4
5class Solution {6    public int minMeetingRooms(int[][] intervals) {7        // Sorting an outer copy preserves the input order and all row values.8        int[][] ordered = intervals.clone();9        Arrays.sort(ordered, (a, b) -> Integer.compare(a[0], b[0]));10        List<Integer> rooms = new ArrayList<>();11        for (int[] cur : ordered) {12            boolean seated = false;13            for (int i = 0; i < rooms.size(); i++) {14                // Equal end/start times permit immediate room reuse.15                if (cur[0] >= rooms.get(i)) {16                    rooms.set(i, cur[1]);17                    seated = true;18                    break;19                }20            }21            if (!seated) {22                rooms.add(cur[1]);23            }24        }25        return rooms.size();26    }27}

Hints

Hint 1

Only the count of simultaneous meetings matters, not which meeting sits in which room.

Hint 2

Splitting every interval into a start event and an end event lets the two kinds be sorted independently.

Hint 3

Sweep the sorted starts against the sorted ends: a start before the earliest end needs a new room, otherwise a room frees up first.

Edge Cases

Back-to-back meetings [1,5] and [5,10] reuse one room, so the answer is 1.
All meetings identical need one room per meeting.
A single meeting needs exactly one room.

Common Mistakes and Interview Tips

Using start <= end to open a room makes [1,5] and [5,10] require two rooms. Start must be strictly earlier; process the end first on equality.
Returning used after the last start rather than best can miss an earlier peak, as in [[0,2],[0,2],[3,4]], whose answer is 2 even though final used is 1.
Subtracting an end and also advancing the start in the same branch skips a start event. Each branch advances only its own pointer.
Sorting the input array in place violates the preserved-input contract of these snippets. Sort copied row references or endpoint arrays.
In JavaScript the default sort orders values as text. Supply a numeric comparator to avoid misordering times such as 2 and 10.

Key Takeaway

Separating starts from ends turns room allocation into event counting: the peak number of open meetings is the minimum number of rooms.