Meeting Rooms II

Explanation & Solution

Description

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required to hold all meetings.

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

Output: 2

Explanation: Meeting [0,30] occupies one room the entire time. Meeting [5,10] overlaps with it, requiring a second room. Meeting [15,20] also overlaps with [0,30] but [5,10] has ended, so only 2 rooms are needed at peak.

Constraints

1 <= intervals.length <= 10^4
0 <= start_i < end_i <= 10^6

Approach

Intervals pattern

1. Create Events from Intervals

For each interval [start, end], create two events:
[start, +1] — a meeting begins, requiring one more room
[end, -1] — a meeting ends, freeing one room
This transforms the interval problem into a timeline of discrete events

2. Sort Events by Time

Sort all events by their time value in ascending order
Tie-breaking rule: if two events share the same time, process end events (-1) before start events (+1)
This ensures that when a meeting ends at the exact time another starts, the room is freed first and can be reused

3. Sweep Through Events

Initialize rooms = 0 (current active meetings) and maxRooms = 0 (peak concurrent meetings)
Walk through the sorted events one by one
For each event, add its delta (+1 or -1) to rooms
Update maxRooms = Math.max(maxRooms, rooms) after each step

4. Return the Maximum

After processing all events, maxRooms holds the highest number of simultaneously active meetings
This is the minimum number of conference rooms required

Key Insight

The event-based sweep line technique avoids comparing every pair of intervals. Instead of asking "which meetings overlap with which?", we ask "at any moment in time, how many meetings are happening?" By sorting events and sweeping left to right, we track the running count in O(n log n) time. The tie-breaking rule (ends before starts) is critical — without it, a meeting ending at time t and one starting at time t would be incorrectly counted as overlapping.

Visualization

Input:

Interval Timeline[[0,30], [5,10], [15,20]]

—

Press play to start visualization

CurrentCompareOverlapMerged

7 steps

Solution Code

Non-overlapping Intervals

Task Scheduler