All problems

Meeting Rooms II

Medium · intervals

You are given a list intervals, where each item [start, end] is one meeting. A meeting occupies a room from start up to, but not including, end.

Return the minimum number of rooms needed so that every meeting gets a room and no two meetings share a room at the same time. A room that frees up at time t can host a meeting that starts at t, so [1, 5] and [5, 9] can use the same room.

The meetings come in no particular order, and there is at least one meeting.

Examples

Example 1

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

Output: 2

[0, 30] runs the whole time. [5, 10] and [15, 20] never overlap each other, so they can share the second room.

Example 2

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

Output: 1

[2, 4] is finished before [7, 10] starts, so one room is enough.

Example 3

Input: intervals = [[1, 5], [5, 9]]

Output: 1

The first meeting frees the room at 5, exactly when the second one begins.

Constraints