Meeting Rooms

Q: How do you solve Meeting Rooms?

Sort the intervals by start time. Iterate through the sorted list, and for each interval, check if its start time is less than the end time of the previous interval. If so, return false immediately. If no overlaps are found, return true after the iteration.

Q: What is the time complexity of Meeting Rooms?

O(n log n). Sorting the intervals dominates the runtime at O(n log n). The subsequent linear scan is O(n), which does not increase the overall complexity.

Q: What pattern does Meeting Rooms use?

The Pattern: Greedy Algorithms (Interval Scheduling Overlap Detection) The Heuristic: Sorting intervals by start time reveals overlaps through a single linear pass, enabling immediate detection of conflicts by comparing adjacent intervals without backtracking or complex data structures.

Easy Greedy Algorithms

Problem

Given an array of meeting time intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings without any overlaps.

0 ≤ intervals.length ≤ 10⁴
intervals[i].length == 2
0 ≤ start_i < end_i ≤ 10⁶

Example

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

Output: false

Sorting intervals by start time yields [[0,30],[5,10],[15,20]]. The first interval ends at 30, which overlaps with the second interval starting at 5, so the person cannot attend all meetings.

Approach

Straightforward Solution

A brute-force approach compares every pair of intervals to check for overlaps, resulting in O(n^2) time complexity, which is inefficient for large inputs.

Core Observation

If any two meetings overlap, the person cannot attend both. Overlaps occur when the start time of a meeting is less than the end time of the previous meeting when intervals are sorted by start time.

Path to Optimal

Preview

Sorting intervals by their start times arranges meetings chronologically. Then, a single linear scan comparing each meeting's start time with the previous meeting's end time detects overlaps efficiently…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Sort the intervals by start time. Iterate through the sorted list, and for each interval, check if its start time is less than the end time of the previous interval…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Sorting the intervals dominates the runtime at O(n log n). The subsequent linear scan is O(n), which does not increase the overall complexity.

Space

O(1)

The sorting can be done in-place, and only a constant amount of extra space is used for variables during iteration.

Pattern Spotlight

Greedy Algorithms (Interval Scheduling Overlap Detection)

Sorting intervals by start time reveals overlaps through a single linear pass, enabling immediate detection of conflicts by comparing adjacent intervals without backtracking or complex data structures.

Solution

Python

1class Solution:
  def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
      intervals.sort(key=lambda i: i[0])
      
      for i in range(1, len(intervals)):
          i1 = intervals[i-1]
          i2 = intervals[i]
          
          if i1[1] > i2[0]:
              return False
      
      return True

Step-by-Step Solution

Sort Intervals by Start Time to Establish Chronological Order

3	`intervals.sort(key=lambda i: i[0])`

Objective

To arrange all meetings in ascending order of their start times, enabling efficient overlap detection.

Key Insight

Sorting intervals by start time transforms the problem into a linear scan for overlaps. This ordering guarantees that any conflicting meetings will be adjacent, eliminating the need for nested comparisons.

Interview Quick-Check

Core Logic

Sorting by start time ensures that overlapping intervals appear consecutively, allowing a single pass to detect conflicts.

Complexity

Sorting takes O(n log n) time, which is the bottleneck of the algorithm.

Detect Overlaps by Comparing Adjacent Intervals

To identify any conflicting meetings by checking if the current meeting starts before the previous meeting ends.

Return True if No Overlaps Are Found After Full Scan

To confirm that all meetings can be attended by returning true when no conflicts are detected.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

if i1[1] > i2[0]:

Check if the previous meeting ends after the current meeting starts, indicating an overlap.

This condition detects the critical conflict where two meetings overlap in time, making it impossible to attend both.

Line 3 Critical

intervals.sort(key=lambda i: i[0])

Sort the intervals in ascending order based on their start times.

Sorting by start time arranges meetings chronologically, which is essential for detecting overlaps efficiently by comparing only adjacent intervals.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why is sorting intervals by start time sufficient to detect all overlaps with a single pass?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Meeting Rooms from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Meeting Rooms drill

or drill a free problem

1	`class Solution:`
2	`def canAttendMeetings(self, intervals: list[list[int]]) -> bool:`
3	`intervals.sort(key=lambda i: i[0])`
4
5	`for i in range(1, len(intervals)):`
6	`i1 = intervals[i-1]`
7	`i2 = intervals[i]`
8
9	`if i1[1] > i2[0]:`
10	`return False`
11
12	`return True`