Skip to main content
Talentd

Meeting Rooms II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersGreedySorting13 min readAsked at: Amazon, Microsoft, Apple +39
Practice this problem

Problem Statement

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

 

Example 1:

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

Example 2:

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

 

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= starti < endi <= 106

Approach Overview

Problem Overview: You receive a list of meeting time intervals [start, end]. Multiple meetings may overlap. The task is to compute the minimum number of conference rooms required so every meeting can run without conflict.

Approach 1: Difference Array (Timeline Sweep) (Time: O(n + R), Space: O(R))

This approach treats time as a timeline and tracks how meetings affect room usage. For every meeting interval, increment the value at start and decrement at end. A prefix sum over the timeline reveals how many meetings are active at each time point. The maximum prefix value equals the number of rooms required. This works because each start adds a room requirement and each end releases one. It’s essentially a sweep-line technique implemented with an array. The limitation is the time range R; if timestamps are very large, allocating a full array becomes inefficient.

Conceptually this mirrors a prefix sum accumulation, so understanding prefix sum patterns helps when implementing the running total.

Approach 2: Difference Using Hash Map (Ordered Events) (Time: O(n log n), Space: O(n))

Instead of allocating a full timeline, store only event changes. For every meeting, record +1 at start and -1 at end inside a map. After processing all meetings, sort the time keys and scan them in order while maintaining a running sum of active meetings. The maximum running sum represents the minimum rooms required. This approach avoids large arrays and works efficiently even when timestamps are large or sparse.

This is essentially the classic sweep-line algorithm frequently used in interval problems. It relies on sorting events, a pattern commonly seen in sorting and array interview questions.

Recommended for interviews: The ordered difference map approach is typically expected in interviews because it handles large ranges without wasting memory. Explaining the difference-array idea first shows you understand the underlying timeline concept. Then transitioning to the map-based sweep line demonstrates practical optimization and strong algorithmic reasoning.

Approach 1: Difference Array

We can implement this using a difference array.

First, we find the maximum end time of all the meetings, denoted as m. Then, we create a difference array d of length m + 1. For each meeting, we add to the corresponding positions in the difference array: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.

Next, we calculate the prefix sum of the difference array and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.

The time complexity is O(n + m) and the space complexity is O(m), where n is the number of meetings and m is the maximum end time.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 2: Difference (Hash Map)

If the meeting times span a large range, we can use a hash map instead of a difference array.

First, we create a hash map d, where we add to the corresponding positions for each meeting's start time and end time: d[l] = d[l] + 1 for the start time, and d[r] = d[r] - 1 for the end time.

Then, we sort the hash map by its keys, calculate the prefix sum of the hash map, and find the maximum value of the prefix sum, which represents the minimum number of meeting rooms required.

The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of meetings.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Difference Array—
Difference (Hash Map)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Difference Array (Timeline)O(n + R)O(R)When the time range is small and bounded, allowing a direct prefix sum over the timeline
Difference with Hash Map (Sweep Line)O(n log n)O(n)General case with large or sparse timestamps where allocating a full timeline is inefficient

Video Solution

Meeting Rooms II - Leetcode 253 - Python • NeetCode • 240,979 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Meeting Rooms II easy or hard?
Meeting Rooms II is generally classified as a medium difficulty problem. The challenge lies in recognizing that overlapping intervals can be converted into chronological events and processed with a sweep-line or priority queue approach.
How to solve Meeting Rooms II in O(n)?
An O(n) style solution is possible if the timeline range is small. Use a difference array: increment at meeting start, decrement at meeting end, and compute a prefix sum across the timeline. The maximum prefix value indicates the required number of rooms. The complexity becomes O(n + R), where R is the time range.
What is the best approach for Meeting Rooms II?
The sweep-line approach using a difference map is the most practical solution. Record +1 at each meeting start and -1 at each meeting end, sort the timestamps, and compute a running sum of active meetings. The maximum running value equals the number of rooms required. This runs in O(n log n) time due to sorting and uses O(n) space.
Is Meeting Rooms II asked at Google/Amazon/Meta?
Meeting Rooms II is a well-known interval scheduling problem frequently reported in interviews at companies like Google, Amazon, Meta, and Microsoft. It tests understanding of sweep-line algorithms, sorting of events, and efficient interval overlap handling.
What data structure is used in Meeting Rooms II?
Common implementations use arrays, hash maps, or heaps depending on the strategy. The sweep-line method uses a map or array to store event changes and a running prefix sum to track active meetings. Heap-based solutions also exist and track the earliest finishing meeting.
What is the time complexity of Meeting Rooms II?
The optimal implementation typically runs in O(n log n) time. The complexity comes from sorting the meeting start and end events before scanning them in chronological order. The scan itself is linear, so the dominant cost is sorting.
Meeting Rooms II Python or Java solution approach?
Both Python and Java implementations usually follow the sweep-line pattern. Insert +1 for each start time and -1 for each end time, sort the keys, and compute the running total of active meetings. The peak value during the scan gives the number of rooms required.

Ready to solve this problem?

Practice Meeting Rooms II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Car Pooling

Next

Meeting Rooms