Log inSign up
mediumLeetCodeNot Started

Meeting Rooms II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required to hold all meetings without conflicts.

Example 1 · Overlapping Meetings:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: Meeting [0, 30] conflicts with [5, 10] and [15, 20]. At time t = 5 to 10, two rooms are in use simultaneously.

Example 2 · Back-to-back Non-overlapping Meetings:

Input: intervals = [[7,10],[2,4]]
Output: 1
Explanation: The meeting [2, 4] ends before [7, 10] starts, so 1 room is sufficient.

Constraints:

  • 1 <= intervals.length <= 104
  • 0 <= start_i < end_i <= 106

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Interval representation and sorting
  • Two Pointers technique
  • Priority Queue / Min-Heap operations

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand peak concurrent interval overlap as a capacity problem.
  • Master Min-Heap simulation for room reuse.
  • Learn the Chronological Two Pointers decoupling pattern for start and end times.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Meeting Rooms IMerge IntervalsMinimum Number of Arrows to Burst Balloons

1. Track Rooms per Meeting (Brute Force)

Intuition

Sort intervals by start time. Maintain a list of active room end times. For each meeting, check existing rooms. If a room has end <= meeting.start, reuse it and update end. Otherwise, allocate a new room.

When to apply: Use to understand room reuse semantics.

Brute Force Room Assignment Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 30, 5, 10, 15, 20]
Current operationSTEP 1 OF 6
Intervals: [[0, 30], [5, 10], [15, 20]]
Visual state
Values and pointers at this exact step
pointers
S
[0,30]
[5,10]
[15,20]
0
↑ M1 [0,30]
1
2
Variables at this step
rooms
[]
Check / comparison
Start with empty room list.
Decision / next transition
Begin room assignments.
Why this step matters

Intervals: [[0, 30], [5, 10], [15, 20]]. Sorted by start: [[0, 30], [5, 10], [15, 20]].

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int minMeetingRooms(int[][] intervals) {
6 if (intervals == null || intervals.length == 0) return 0;
7 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
8 List<Integer> rooms = new ArrayList<>();
9
10 for (int[] interval : intervals) {
11 boolean allocated = false;
12 for (int i = 0; i < rooms.size(); i++) {
13 if (rooms.get(i) <= interval[0]) {
14 rooms.set(i, interval[1]);
15 allocated = true;
16 break;
17 }
18 }
19 if (!allocated) {
20 rooms.add(interval[1]);
21 }
22 }
23 return rooms.size();
24 }
25 }
26
27 public static void main(String[] args) {
28 Solution sol = new Solution();
29 int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
30 System.out.println("Min meeting rooms: " + sol.minMeetingRooms(intervals));
31 }
32}

Time & Space Complexity

  • Time complexity: O(n^2) — Sorting takes O(n log n). For each of n meetings, scanning up to n existing rooms takes O(n2).
  • Space complexity: O(n) — List of rooms stores up to n end times.

Why Brute Force Doesn't Scale:

For N = 10,000, N2 requires 100 million comparisons.

Two pointers sorting requires only ~140,000 operations (700x faster) and avoids heap node allocations.

2. Min-Heap of End Times

Intuition

Sort meetings by start time. Push the first meeting's end time to a min-heap. For each subsequent meeting: if min-heap.top() <= start, pop it (room freed). Push new meeting's end time. Min-heap size is the answer.

When to apply: Use when an online stream of meetings arrives.

Min-Heap End Times Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 30, 5, 10, 15, 20]
Current operationSTEP 1 OF 6
Sort intervals: [[0, 30], [5, 10], [15, 20]]
Visual state
Values and pointers at this exact step
pointers
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
[0,30]
[5,10]
[15,20]
0
↑ Heap [30]
1
2
Binary Heap Tree Topology
[0,30]#0
[5,10]#1
[15,20]#2
Variables at this step
heap
[30]
Check / comparison
Start with M1 [0, 30].
Decision / next transition
Push end time 30 into min-heap.
Why this step matters

Sort intervals: [[0, 30], [5, 10], [15, 20]]. Initialize empty min-heap.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int minMeetingRooms(int[][] intervals) {
6 if (intervals == null || intervals.length == 0) return 0;
7 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
8 PriorityQueue<Integer> pq = new PriorityQueue<>();
9
10 pq.add(intervals[0][1]);
11 for (int i = 1; i < intervals.length; i++) {
12 if (intervals[i][0] >= pq.peek()) {
13 pq.poll();
14 }
15 pq.add(intervals[i][1]);
16 }
17 return pq.size();
18 }
19 }
20
21 public static void main(String[] args) {
22 Solution sol = new Solution();
23 int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
24 System.out.println("Min meeting rooms: " + sol.minMeetingRooms(intervals));
25 }
26}

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting takes O(n log n). Heap push/pop takes O(log n) for each of n meetings.
  • Space complexity: O(n) — Min-heap stores up to n end times.

3. Chronological Two Pointers (Optimal & Standard)

Intuition

1. Extract start times and end times into two separate arrays; sort both. 2. Initialize s_ptr = 0, e_ptr = 0, rooms = 0, maxRooms = 0. 3. If starts[s_ptr] < ends[e_ptr], a meeting started before the earliest ending one finished: rooms++, maxRooms = max(maxRooms, rooms), s_ptr++. 4. Otherwise, a meeting ended: rooms--, e_ptr++. Repeat until all meetings start.

When to apply: Use as the clean StudyVex-Standard optimal approach without complex heap data structures.

Chronological Start & End Pointer Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 5, 15, 10, 20, 30]
Current operationSTEP 1 OF 6
Sort starts: [0, 5, 15]
Visual state
Values and pointers at this exact step
pointers
S
0
5
15
10
20
30
0
↑ s_ptr (0)
1
2
3
↑ e_ptr (10)
4
5
Variables at this step
s_ptr
0
e_ptr
0
rooms
0
maxRooms
0
Check / comparison
Initialize chronological pointers.
Decision / next transition
Evaluate earliest start vs earliest end.
Why this step matters

Sort starts: [0, 5, 15]. Sort ends: [10, 20, 30]. s_ptr = 0, e_ptr = 0, rooms = 0, maxRooms = 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int minMeetingRooms(int[][] intervals) {
6 if (intervals == null || intervals.length == 0) return 0;
7 int n = intervals.length;
8 int[] starts = new int[n];
9 int[] ends = new int[n];
10
11 for (int i = 0; i < n; i++) {
12 starts[i] = intervals[i][0];
13 ends[i] = intervals[i][1];
14 }
15
16 Arrays.sort(starts);
17 Arrays.sort(ends);
18
19 int s = 0, e = 0, rooms = 0, maxRooms = 0;
20 while (s < n) {
21 if (starts[s] < ends[e]) {
22 rooms++;
23 maxRooms = Math.max(maxRooms, rooms);
24 s++;
25 } else {
26 rooms--;
27 e++;
28 }
29 }
30 return maxRooms;
31 }
32 }
33
34 public static void main(String[] args) {
35 Solution sol = new Solution();
36 int[][] intervals = {{0, 30}, {5, 10}, {15, 20}};
37 System.out.println("Min meeting rooms: " + sol.minMeetingRooms(intervals));
38 }
39}

Time & Space Complexity

  • Time complexity: O(n log n) — Sorting start and end arrays takes O(n log n). The two-pointer linear pass takes O(n).
  • Space complexity: O(n) — O(n) memory to store the start and end arrays.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Point-in-time Overlap CheckO(N^2)O(1)For each interval, check how many other intervals overlap with its start time.Repeated pairwise interval overlap comparisons.
2.Better — Min-Heap (Priority Queue) of End TimesO(N log N)O(N)Sort intervals by start time. Push end times into a Min-Heap. If heap.top() <= interval[0], pop the top (room freed). Push current end time. Final heap size is rooms needed.Priority queue push/pop operations.
3.Optimal — Chronological Two Pointers on Sorted Start/End ArraysOptimalO(N log N)O(N)Extract start and end arrays, sort both. Advance start pointer: if start[s] < end[e], increment room count; otherwise advance e pointer.Sorting start and end arrays (optimal).

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Meeting Rooms II?

2.Why is the brute force approach suboptimal for large inputs in Meeting Rooms II?

3.Which data structure or technique enables the optimal solution for Meeting Rooms II?

Back to DSA Sheet