Skip to main content

253. Meeting Rooms II

medium

Given a list of meeting intervals, find the minimum number of rooms required. A FAANG classic that becomes elegant once you reach for a min-heap of end times.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

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

Examples

Example 1

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

Explanation: Meeting [0,30] needs a room. [5,10] overlaps with it, so a second room is needed. [15,20] starts after [5,10] ends — it reuses that room. Maximum concurrent meetings = 2.

Example 2

Input
intervals = [[7,10],[2,4]]
Output
1

Explanation: The two meetings don't overlap; one room handles both.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Sort intervals by start time. Process them in that order.

Hint 2

At each new meeting, ask: is any room free? A room is free if its current meeting's end time is at or before the new meeting's start.

Hint 3

Keep a min-heap of end times. The smallest end time is the earliest a room will free up.

Hint 4

If the new meeting starts at or after the heap's min, pop (reuse that room) and push the new end. Otherwise allocate a new room (just push). The heap size at any moment is the rooms in use; max heap size is the answer.

Solution approach

Reveal approach

Sort intervals by start time. Maintain a min-heap of end times of currently-occupied rooms. For each interval in start order: if the heap is non-empty and its min end-time is at or before this meeting's start, pop (the room is free and we reuse it). Push this meeting's end time. The answer is the maximum heap size observed — or equivalently, the heap size at the end, because we only pop one room per iteration and push exactly one. O(n log n) total: sorting dominates, each heap op is O(log n). The min-heap is the key insight — you want to ask 'which room frees up soonest' efficiently. Alternative: chronological event sweep (sort starts and ends separately, walk both pointers) avoids the heap but is harder to reason about.

Complexity

Time
O(n log n)
Space
O(n)

Related patterns

  • heap
  • intervals
  • sorting
  • greedy

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Bloomberg
  • Apple

More Heaps practice problems

See all Heaps problems →