How do you approach Meeting Rooms II (Minimum Rooms)?

The answer is the maximum number of meetings in progress at any single instant.

What is the time complexity of Meeting Rooms II (Minimum Rooms)?

Time complexity: O(n log n) for the two sorts.. Space complexity: O(n).

What are common mistakes on Meeting Rooms II (Minimum Rooms)?

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else. Treating touching intervals as overlapping (or not) without checking which the problem means. Mutating the input intervals while iterating over them.

gitGood.dev

← Back to problems

Meeting Rooms II (Minimum Rooms)

MediumAlgorithms

Description

Given an array of meeting time intervals [start, end], return the minimum number of conference rooms required to hold them all.

A room is reusable the moment its meeting ends: a meeting ending at 10 and another starting at 10 can share one room.

Example 1

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

Output: 2

Example 2

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

Output: 1

Example 3

Input: intervals = [[1,5],[2,6],[3,7],[4,8]]

Output: 4

Constraints

- 0 <= intervals.length <= 10^4 - 0 <= start < end <= 10^6

Meeting Rooms II (Minimum Rooms): approach, complexity and pitfalls

A medium intervals problem, graded against 6 test cases (3 of them hidden).

The pattern: Intervals

Sorting by start or end, then merging or scheduling overlapping ranges.

Reach for it when you see: Meetings, bookings, ranges, or anything with a start and an end.

If you are stuck

Show the 3-step hint ladder

The answer is the maximum number of meetings in progress at any single instant.
Separate the starts and the ends into two sorted lists. Sweep them together: a start consumes a room, an end frees one.
Process an end before a start when the times are equal - that is what lets a room be reused back-to-back.

The optimal approach

Show the approach: The answer is a peak, not a total

Rooms needed at any instant equals meetings in progress at that instant, so the answer is the maximum concurrency over the timeline.

The sweep-line version: pull the start times and end times into two separate sorted arrays, then walk them with two pointers. Each start increments a counter, each end decrements it, and the answer is the largest value the counter reaches. Decoupling starts from ends is the trick - after sorting, it no longer matters which start paired with which end, only how they interleave.

When a start and an end share a timestamp, process the end first, so the freed room is reused rather than a new one allocated. That is the difference between `[[1,2],[2,3]]` needing 1 room and 2.

The equivalent min-heap formulation keeps the end times of active meetings and pops those that have finished; both are O(n log n) and interviewers accept either. The two-pointer version avoids the heap entirely.

Time: O(n log n) for the two sorts.
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Intervals mistakes

These apply to the pattern as a whole, not just this problem.

Not sorting first. Nearly every interval algorithm assumes the list is ordered by start, and skipping that step gives answers that are right on the sample and wrong everywhere else.
Treating touching intervals as overlapping (or not) without checking which the problem means.
Mutating the input intervals while iterating over them.