DSA Tracker

Visualize

Meeting Rooms II

time O(n log n)space O(n)

The insight: the number of rooms needed is just the peak number of meetings happening at the same instant — no need to simulate assigning meetings to specific rooms, just track how high the overlap gets. Sorting starts and ends separately and sweeping through them as a timeline of "a meeting began" / "a meeting ended" events does exactly that: whenever a new start arrives before the earliest still-unfinished meeting has ended, that's one more room needed right now; once a start arrives after that earliest end, a room has already freed up and can be reused instead. Starts: [0,5,15], Ends: [10,20,30] — two meetings are already running (started at 0 and 5) before either finishes at 10, so the peak of 2 rooms happens right at the start, and no later start ever needs a third.

Details

Animated on: Given an array of intervals representing meeting time ranges, find the minimum number of conference rooms required so that all meetings can be hosted without overlap.

Problem:Meeting Rooms IIMedium

Pattern:Intervals

Intervals

step 1 / 5

0
[0]
5
[1]
15
[2]

Initialize starts=[0,5,15], ends=[10,20,30]. rooms=0, endIdx=0, i=0.

  • i=0· arr[0] = 0
Pseudocode
1FUNCTION minMeetingRooms(intervals):
2  starts = all start times, sorted ascending
3  ends = all end times, sorted ascending
4  rooms = 0, endIdx = 0
5  FOR i from 0 to length of starts - 1:
6    IF starts[i] < ends[endIdx]:
7      add one to rooms   (a meeting began before any freed up)
8    ELSE:
9      move endIdx one step right   (a room freed up, reuse it)
10    END IF
11  END FOR
12  RETURN rooms
13END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 5 steps
  1. Initialize starts=[0,5,15], ends=[10,20,30]. rooms=0, endIdx=0, i=0.
  2. i=0: start=0 < ends[endIdx=0]=10? Yes → need new room. rooms=1.
  3. i=1: start=5 < ends[endIdx=0]=10? Yes → need new room. rooms=2.
  4. i=2: start=15 >= ends[endIdx=0]=10 → NOT less-than, so a room frees up instead: endIdx becomes 1 (now tracking ends[1]=20). rooms stays 2.
  5. All 3 starts examined, loop ends. Peak overlap was 2 (meetings [0,30] and [5,10] both active at once). Answer: 2 rooms needed.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Meeting Rooms II in the editorAll Intervals problemsBack to roadmap