Meeting Rooms

Difficulty: Easy Source: NeetCode

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings (i.e., no two meetings overlap).

Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: false

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

Constraints:

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i < end_i <= 10^6

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorting — sorting intervals by start time to bring potentially conflicting meetings next to each other
• Intervals — knowing that two intervals [a,b] and [c,d] (with a ≤ c) overlap whenever c < b

1. Brute Force

Intuition

Check every pair of meetings to see if any two overlap. If the start of one meeting falls inside another, it is a conflict. This is straightforward but quadratic — fine for small inputs, but we can do better.

Algorithm

1. For every pair (i, j) with i < j:
   • If intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1], there is an overlap — return False.
2. If no pair overlaps, return True.

Solution

def can_attend_meetings_brute(intervals):
    n = len(intervals)
    for i in range(n):
        for j in range(i + 1, n):
            a_start, a_end = intervals[i]
            b_start, b_end = intervals[j]
            # Two intervals overlap iff each starts before the other ends
            if a_start < b_end and b_start < a_end:
                return False
    return True


print(can_attend_meetings_brute([[0,30],[5,10],[15,20]]))  # False
print(can_attend_meetings_brute([[7,10],[2,4]]))           # True
print(can_attend_meetings_brute([]))                       # True
print(can_attend_meetings_brute([[5,8],[9,15]]))           # True

Complexity

• Time: O(n²) — all pairs
• Space: O(1)

2. Sort by Start Time

Intuition

Once we sort meetings by start time, any overlap must occur between two adjacent meetings in the sorted order. If meeting i ends after meeting i+1 starts, there is a conflict. A single pass after sorting is enough — we never need to compare non-adjacent pairs.

Algorithm

1. Sort intervals by start time.
2. For each consecutive pair (intervals[i], intervals[i+1]):
   • If intervals[i][1] > intervals[i+1][0], return False (the current meeting has not ended when the next one starts).
3. Return True.

Solution

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])

    for i in range(len(intervals) - 1):
        # If current meeting ends after the next one starts — conflict
        if intervals[i][1] > intervals[i + 1][0]:
            return False

    return True


print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False
print(can_attend_meetings([[7,10],[2,4]]))           # True
print(can_attend_meetings([]))                       # True
print(can_attend_meetings([[5,8],[9,15]]))           # True
print(can_attend_meetings([[5,8],[8,15]]))           # True  (touching is OK)

Complexity

• Time: O(n log n) — sorting dominates
• Space: O(1) — in-place sort, constant extra variables

Common Pitfalls

Using >= instead of > for the overlap check. Meetings that only touch at a boundary ([5,8] and [8,10]) do NOT conflict — the first ends exactly when the second begins. Use strict > so touching meetings are allowed.

Forgetting to handle an empty list. When intervals is empty, the loop body never executes and True is returned correctly — but make sure your code does not index into an empty list before the loop.

Not sorting before scanning. Without sorting, a late-starting meeting could appear before an early-starting one, making adjacent comparisons miss real conflicts.