Meeting Rooms II solution and explanation
Google
9 more videos on this problem
Meeting Rooms II - Leetcode 253 - PythonNeetCode · 11:46 · 240K views
Meeting Rooms II - LeetCode 253 PythonDeepti Talesra · 14:01 · 8K views
Meeting Rooms II - LeetCode 253 - JavaScriptAlgoJS · 6:38 · 3K views
Meeting Rooms II | LeetCode #253 | Python 3 | Easy to UnderstandCoding With Jaz · 10:43 · 2K views
Meeting Rooms II | LeetCode 253 (Medium)Destination FAANG · 15:59 · 1K views
LeetCode 253. Meeting Rooms IISrinu Nampalli @Algo2Design · 3:38 · 1K views
Meeting Rooms II - LeetCode 253 - Java - Two PointersCoding Interview Patterns · 10:06 · 1K views
LeetCode 253. Meeting Rooms IIHappy Coding · 13:00 · 742 views
Meeting Rooms II - LeetCode 253 - JavaScott Hacks Code · 6:50 · 482 views
253. Meeting Rooms II - Week 3/5 Leetcode March ChallengeProgramming Live with Larry · 11:03 · 411 views
The problem
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 <= 1040 <= 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.
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
m = max(e[1] for e in intervals)
d = [0] * (m + 1)
for l, r in intervals:
d[l] += 1
d[r] -= 1
ans = s = 0
for v in d:
s += v
ans = max(ans, s)
return ansclass Solution {
public int minMeetingRooms(int[][] intervals) {
int m = 0;
for (var e : intervals) {
m = Math.max(m, e[1]);
}
int[] d = new int[m + 1];
for (var e : intervals) {
++d[e[0]];
--d[e[1]];
}
int ans = 0, s = 0;
for (int v : d) {
s += v;
ans = Math.max(ans, s);
}
return ans;
}
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
int m = 0;
for (const auto& e : intervals) {
m = max(m, e[1]);
}
vector<int> d(m + 1);
for (const auto& e : intervals) {
d[e[0]]++;
d[e[1]]--;
}
int ans = 0, s = 0;
for (int v : d) {
s += v;
ans = max(ans, s);
}
return ans;
}
};function minMeetingRooms(intervals: number[][]): number {
const m = Math.max(...intervals.map(([_, r]) => r));
const d: number[] = Array(m + 1).fill(0);
for (const [l, r] of intervals) {
d[l]++;
d[r]--;
}
let [ans, s] = [0, 0];
for (const v of d) {
s += v;
ans = Math.max(ans, s);
}
return ans;
}func minMeetingRooms(intervals [][]int) (ans int) {
m := 0
for _, e := range intervals {
m = max(m, e[1])
}
d := make([]int, m+1)
for _, e := range intervals {
d[e[0]]++
d[e[1]]--
}
s := 0
for _, v := range d {
s += v
ans = max(ans, s)
}
return
}impl Solution {
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
let mut m = 0;
for e in &intervals {
m = m.max(e[1]);
}
let mut d = vec![0; (m + 1) as usize];
for e in intervals {
d[e[0] as usize] += 1;
d[e[1] as usize] -= 1;
}
let mut ans = 0;
let mut s = 0;
for v in d {
s += v;
ans = ans.max(s);
}
ans
}
}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.
class Solution:
def minMeetingRooms(self, intervals: List[List[int]]) -> int:
d = defaultdict(int)
for l, r in intervals:
d[l] += 1
d[r] -= 1
ans = s = 0
for _, v in sorted(d.items()):
s += v
ans = max(ans, s)
return ansclass Solution {
public int minMeetingRooms(int[][] intervals) {
Map<Integer, Integer> d = new TreeMap<>();
for (var e : intervals) {
d.merge(e[0], 1, Integer::sum);
d.merge(e[1], -1, Integer::sum);
}
int ans = 0, s = 0;
for (var e : d.values()) {
s += e;
ans = Math.max(ans, s);
}
return ans;
}
}class Solution {
public:
int minMeetingRooms(vector<vector<int>>& intervals) {
map<int, int> d;
for (const auto& e : intervals) {
d[e[0]]++;
d[e[1]]--;
}
int ans = 0, s = 0;
for (auto& [_, v] : d) {
s += v;
ans = max(ans, s);
}
return ans;
}
};function minMeetingRooms(intervals: number[][]): number {
const d: { [key: number]: number } = {};
for (const [l, r] of intervals) {
d[l] = (d[l] || 0) + 1;
d[r] = (d[r] || 0) - 1;
}
let [ans, s] = [0, 0];
const keys = Object.keys(d)
.map(Number)
.sort((a, b) => a - b);
for (const k of keys) {
s += d[k];
ans = Math.max(ans, s);
}
return ans;
}func minMeetingRooms(intervals [][]int) (ans int) {
d := make(map[int]int)
for _, e := range intervals {
d[e[0]]++
d[e[1]]--
}
keys := make([]int, 0, len(d))
for k := range d {
keys = append(keys, k)
}
sort.Ints(keys)
s := 0
for _, k := range keys {
s += d[k]
ans = max(ans, s)
}
return
}use std::collections::HashMap;
impl Solution {
pub fn min_meeting_rooms(intervals: Vec<Vec<i32>>) -> i32 {
let mut d: HashMap<i32, i32> = HashMap::new();
for interval in intervals {
let (l, r) = (interval[0], interval[1]);
*d.entry(l).or_insert(0) += 1;
*d.entry(r).or_insert(0) -= 1;
}
let mut times: Vec<i32> = d.keys().cloned().collect();
times.sort();
let mut ans = 0;
let mut s = 0;
for time in times {
s += d[&time];
ans = ans.max(s);
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Difference Array | – |
| Difference (Hash Map) | – |
Complexity analysis
| Approach | Time | Space | When 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 |
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.