Google · Coding 3 of 3

Meeting Rooms II

Find the minimum number of rooms needed for a list of meetings.

MediumIntervalsHeapSortingBest: O(n log n) time · O(n) space

Practice question: an editorial practice prompt, not a claim that Google asks this exact question. Interviews vary by role, level, team, and location.

Problem

Problem statement

Given an array of meeting times intervals where intervals[i] = [start, end], return the minimum number of conference rooms needed so that no two meetings share a room at the same time.

A meeting that ends at time t frees its room for a meeting that starts at t.

Examples

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

Why: The 0–30 meeting needs its own room; the other two can share one.

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

Why: The meetings never overlap.

Example 3
Input
intervals = [[1, 5], [5, 10]]
Output
1

Why: Back-to-back meetings can use the same room.

Constraints

  • 1 ≤ intervals.length ≤ 10⁴
  • 0 ≤ start < end ≤ 10⁶
In the interview

How to answer it out loud

What it tests: Interval reasoning, choosing a heap for the right reason, and precise boundary rules.

  1. 1
    Clarify

    Clarify whether a meeting ending at t can share a room with one starting at t, and whether the input is sorted.

  2. 2
    Implement

    Sort meetings by start; keep a min-heap of end times and reuse the earliest-ending room when it is free.

  3. 3
    Verify

    Test back-to-back meetings, nested meetings, and a single meeting; explain O(n log n) time.

Approaches

From brute force to the best solution

ApproachIdeaTimeSpace
Count overlaps per meetingFor each meeting start, count the meetings running at that moment.O(n²)O(1)
Sort + min-heap of end timesBestProcess meetings by start; reuse the room that frees up earliest if it is free.O(n log n)O(n)
Two sorted arraysSort starts and ends separately; walk both and track rooms in use.O(n log n)O(n)
Key insight

Only the room that frees up earliest matters when a new meeting starts. A min-heap of end times gives you that room in O(log n), and its final size is the number of rooms opened.

Solution

Reference solution

Each version is self-contained and has been run against the examples and test cases on this page.

import heapq​​def min_meeting_rooms(intervals: list[list[int]]) -> int:    ends = []                               # min-heap: end times of rooms in use    for start, end in sorted(intervals):        if ends and ends[0] <= start:       # earliest-ending room is free: reuse it            heapq.heapreplace(ends, end)        else:            heapq.heappush(ends, end)       # every room is busy: open a new one    return len(ends)
Time
O(n log n)
Space
O(n)
Approach
Sort + min-heap of end times
Test cases

Edge cases to run before you say “done”

InputExpectedWhy it matters
[[1, 5], [5, 10]]1Use <=, not <, when checking the earliest end.
[[1, 10], [2, 7], [3, 19], [8, 12], [10, 20], [11, 30]]4Peak overlap is at time 11.
[[5, 8]]1A single meeting.
Likely follow-ups

Answer the main question first, then take these on one at a time:

  • Can you also return which room each meeting uses?
  • How would you solve it with two sorted arrays instead of a heap?
  • What changes if meetings arrive in real time?
Avoid these mistakes

Check your recording or written solution against this list:

  • Using < instead of <= for back-to-back meetings
  • Forgetting to sort by start time
  • Counting total overlaps instead of the peak
Sources and methodology

This guide combines general interview-practice patterns with the public hiring material below. The practice prompt and coaching are PiriPiri AI editorial content, not official Google questions or answers.

Google Careers: how we hire ↗
Official sources reviewed 20 September 2026.