Log inSign up
easyLeetCodeNot Started

Meeting Rooms

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 where intervals[i] = [start_i, end_i], determine if a person could attend all meetings.

Note that meetings starting exactly when the previous meeting ends (e.g. [0, 8] and [8, 10]) do not conflict.

Example 1 · Conflicting Intervals:

Input: intervals = [[0, 30], [5, 10], [15, 20]]
Output: false
Explanation: The meeting [0, 30] overlaps with [5, 10] and [15, 20]. A person cannot attend both [0, 30] and [5, 10].

Example 2 · Non-Conflicting Consecutive Intervals:

Input: intervals = [[7, 10], [2, 4]]
Output: true
Explanation: Sorted intervals: [[2, 4], [7, 10]]. Since 4 <= 7, there is no overlap. The person can attend both.

Example 3 · Adjacent Meetings Sharing Endpoint:

Input: intervals = [[0, 8], [8, 10]]
Output: true
Explanation: One meeting ends at 8 and the next starts at 8. They do not conflict, so the person can attend both.

Constraints:

  • 0 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= start_i < end_i <= 106

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Understanding intervals [start, end] and overlap conditions
  • Custom comparator sorting on 2D arrays/vectors
  • Interval scheduling fundamentals

What You'll Learn

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

  • Master interval sorting using start time comparators.
  • Formulate the overlap condition: start2 < end1.
  • Evaluate trade-offs between quadratic pairwise checks vs sorted adjacent scans.
  • Write clean implementations in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

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

Signals to Look For:

  • Problem gives a collection of intervals [start, end] and checks for any overlapping pairs.
  • Unsorted intervals can start at arbitrary times.
  • The overlap condition between two sorted intervals is next.start < curr.end.

Algorithmic Decision Tree:

  • Whenever dealing with interval conflicts or merges: Sort intervals by start time ascending, then check consecutive elements in a single linear pass.

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Compare Every Pair for Overlap

Intuition

Compare every pair of intervals (i, j) to check if interval i and interval j overlap.

Algorithm

  1. 1. Let n = intervals.length.
  2. 2. For i from 0 to n-1: - For j from i+1 to n-1: - If max(intervals[i][0], intervals[j][0]) < min(intervals[i][1], intervals[j][1]), return false.
  3. 3. If no overlaps found, return true.

All Pairs Overlap Comparison (O(N^2))

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
Phase 1 — Pair (0, 1): Compare intervals[0] = [0, 30] and intervals[1] = [5, 10]
Visual state
Values and pointers at this exact step
array
S
[0, 30]
[5, 10]
[15, 20]
0
↑ Collision!
1
2
Variables at this step
Pair
[0, 30] vs [5, 10]
Overlap
true
Check / comparison
5 < 10: Overlap detected!
Decision / next transition
Meeting room collision between [0, 30] and [5, 10].
Why this step matters

Phase 1 — Pair (0, 1): Compare intervals[0] = [0, 30] and intervals[1] = [5, 10]. Check overlap: max(0, 5) < min(30, 10) => 5 < 10 is TRUE!

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool canAttendMeetings(vector<vector<int>>& intervals) {
17 int n = intervals.size();
18 for (int i = 0; i < n; ++i) {
19 for (int j = i + 1; j < n; ++j) {
20 if (max(intervals[i][0], intervals[j][0]) < min(intervals[i][1], intervals[j][1])) {
21 return false;
22 }
23 }
24 }
25 return true;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
32 bool ans = sol.canAttendMeetings(intervals);
33 cout << "Can Attend Meetings: " << (ans ? "true" : "false") << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N^2) — Nested loops test all N*(N-1)/2 pairs in O(N2) time.
  • Space complexity: O(1) — Auxiliary space is O(1).

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Min-Heap / Event Point Simulation

Intuition

Sort start and end points as independent timeline events and track concurrent active rooms.

Algorithm

  1. 1. Create event list: For [s, e], add (s, +1) and (e, -1).
  2. 2. Sort events primarily by timestamp. If timestamps match, end events (-1) come before start events (+1).
  3. 3. Iterate through events maintaining count activeRooms. If activeRooms > 1, return false.
  4. 4. Return true.

Min-Heap / Event Point Sweep Line

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
Phase 1 — Sort Intervals by Start Time: intervals = [[0, 30], [5, 10], [15, 20]]
Visual state
Values and pointers at this exact step
array
Array Buffer RepresentationParent i → Left 2i+1, Right 2i+2
S
[0, 30]
[5, 10]
[15, 20]
0
↑ Start
1
2
Binary Heap Tree Topology
[0, 30]#0
[5, 10]#1
[15, 20]#2
Variables at this step
Heap
[]
Time
0
Check / comparison
Sorted by start time.
Decision / next transition
Begin event processing.
Why this step matters

Phase 1 — Sort Intervals by Start Time: intervals = [[0, 30], [5, 10], [15, 20]]. Initialize min-heap of end times.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool canAttendMeetings(vector<vector<int>>& intervals) {
17 vector<pair<int, int>> events;
18 for (const auto& iv : intervals) {
19 events.push_back({iv[0], 1});
20 events.push_back({iv[1], -1});
21 }
22 sort(events.begin(), events.end(), [](const auto& a, const auto& b) {
23 if (a.first != b.first) return a.first < b.first;
24 return a.second < b.second;
25 });
26 int active = 0;
27 for (const auto& ev : events) {
28 active += ev.second;
29 if (active > 1) return false;
30 }
31 return true;
32 }
33};
34
35int main() {
36 Solution sol;
37 vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
38 bool ans = sol.canAttendMeetings(intervals);
39 cout << "Can Attend Meetings: " << (ans ? "true" : "false") << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting 2N events takes O(N log N) time. Linear sweep takes O(N).
  • Space complexity: O(N) — Auxiliary list stores 2N event points, taking O(N) memory.

3. Sort by Start Time & Consecutive Check (Optimal)

Intuition

Sort intervals by start time ascending, then check if any interval starts before the previous one ends.

Algorithm

  1. 1. Sort intervals by start time ascending: intervals.sort((a, b) => a[0] - b[0]).
  2. 2. For i from 1 to intervals.length - 1: - If intervals[i][0] < intervals[i-1][1], return false (current meeting starts before previous ends).
  3. 3. Return true. Optimal O(N log N) time and O(1) extra space.

Sort by Start Time & Consecutive Check (O(1) Space)

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
Phase 1 — Sort by Start Times: Sort intervals ascending by start time: [[0, 30], [5, 10], [15, 20]]
Visual state
Values and pointers at this exact step
array
S
[0, 30]
[5, 10]
[15, 20]
0
↑ Prev
1
↑ Curr
2
Variables at this step
Sorted
[[0, 30], [5, 10], [15, 20]]
i
1
Check / comparison
Sorting completes in O(N log N).
Decision / next transition
Begin consecutive pair check from i = 1.
Why this step matters

Phase 1 — Sort by Start Times: Sort intervals ascending by start time: [[0, 30], [5, 10], [15, 20]]. Once sorted, overlaps can ONLY occur between consecutive intervals!

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5#include <unordered_map>
6#include <unordered_set>
7#include <queue>
8#include <stack>
9#include <numeric>
10#include <climits>
11
12using namespace std;
13
14class Solution {
15public:
16 bool canAttendMeetings(vector<vector<int>>& intervals) {
17 sort(intervals.begin(), intervals.end());
18 for (size_t i = 1; i < intervals.size(); ++i) {
19 if (intervals[i][0] < intervals[i - 1][1]) {
20 return false;
21 }
22 }
23 return true;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<vector<int>> intervals = {{0, 30}, {5, 10}, {15, 20}};
30 bool ans = sol.canAttendMeetings(intervals);
31 cout << "Can Attend Meetings: " << (ans ? "true" : "false") << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(N log N) — Sorting takes O(N log N) time. The single adjacent comparison pass takes O(N) time.
  • Space complexity: O(1) — In-place sort uses O(1) auxiliary space.

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Approach 1: Compare Every Pair for OverlapO(N^2)O(1)Compare every pair of intervals (i, j) to check if interval i and interval j overlap.Repeated redundant scans over the input.
2.Approach 2: Min-Heap / Event Point SimulationO(N log N)O(N)Sort start and end points as independent timeline events and track concurrent active rooms.Auxiliary memory allocation or sorting step.
3.Approach 3: Sort by Start Time & Consecutive Check (Optimal)OptimalO(N log N)O(1)Sort intervals by start time ascending, then check if any interval starts before the previous one ends.None. Asymptotically 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:

  • Consecutive Meetings Sharing Boundary — Input: intervals = [[1, 5], [5, 10]], Expected: true — Meeting ends at 5 and next begins at 5. They do not overlap; 5 < 5 is false.
  • Empty or Single Interval — Input: intervals = [], Expected: true — 0 or 1 meeting can always be attended without conflict.
  • Complete Enclosure — Input: intervals = [[1, 100], [2, 3]], Expected: false — Interval [2, 3] is completely inside [1, 100]; conflict detected immediately.

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?

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

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

Back to DSA Sheet