Minimum Meeting Rooms

Hard·Tagsarraytwo-pointerssortinggreedy

Problem Statement

Given a list of intervals representing the start and end times of `N` meetings, find the minimum number of meeting rooms required to hold all the meetings. Each interval is represented as an array `[start, end]`.

Examples

Example 1

Input

intervals: [[1, 4], [2, 5], [7, 9]]

Timeline

Output

"2"

Why

Since [1, 4] and [2, 5] overlap, we need two separate rooms to hold these two meetings. The third meeting [7, 9] can be held in either of the two rooms.

Example 2

Input

intervals: [[6, 7], [2, 4], [8, 12]]

Timeline

Output

"1"

Why

None of the meetings overlap, therefore we only need one room.

Example 3

Input

intervals: [[1, 4], [2, 3], [3, 6]]

Timeline

Output

"2"

Why

Since [1, 4] overlaps with both [2, 3] and [3, 6], we need two rooms to accommodate them.

Example 4

Input

intervals: [[4, 5], [2, 3], [2, 4], [3, 5]]

Timeline

Output

"2"

Why

At time 3, the active meetings are [2, 4] and [3, 5]. We will need a maximum of two rooms to hold all the meetings.

Constraints

•1 <= intervals.length <= 10000
•intervals[i].length == 2
•0 <= start < end <= 100000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

To solve this problem, we don't necessarily need to track the meetings as continuous blocks. We only care about the moments a meeting *starts* (we need a room) and the moments a meeting *ends* (a room frees up).

Hint 2

What happens if you extract all the start times into one array, and all the end times into another array?

Hint 3

If you sort both arrays independently, you can use two pointers to walk through time chronologically. If `start[s] < end[e]`, a meeting is starting, so you need a room. If `start[s] >= end[e]`, a meeting has ended, so a room is freed!