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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Meeting Rooms II and Heaps problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →