LeetCode 252 · Intervals

Meeting Rooms, explained with a picture

Can one person attend every meeting?.

EasyIntervals
▶ Watch it step by step

The problem

Given meeting times, can one person attend all of them (no two overlap)?

Input:  [0,30] [5,10] [15,20]
Output: false

Picture it

Picture one person’s calendar. Sort the meetings by start time. If any meeting starts before the previous one has ended, there’s a clash, and the person can’t attend both.

How to recognise it

  • The question is yes or no: does any pair of intervals overlap?
  • Checking every pair works but is slow. After sorting by start, an overlap anywhere always shows up as an overlap between neighbours, so one pass over adjacent pairs is enough.
  • Meetings are [start, end] where a meeting ending at 10 and one starting at 10 do not clash: the person walks straight from one to the other.
  • Up to 10^4 meetings (on LeetCode, where this is a premium problem), so O(n log n) is the target.
  • This is the simplest of the interval family. Meeting Rooms II asks how many rooms you need instead of whether one is enough.

Start with brute force

Compare every pair of meetings. Two meetings overlap when each starts before the other ends.

def can_attend_brute(intervals):
    for i in range(len(intervals)):
        for j in range(i + 1, len(intervals)):
            a, b = intervals[i], intervals[j]
            if a[0] < b[1] and b[0] < a[1]:      # they overlap
                return False
    return True

There are n(n − 1)/2 pairs, so time is O(n²) and space O(1). For 10^4 meetings that is about 5 × 10^7 checks when there is no clash, which takes several seconds in Python.

From brute force to the idea

  1. Find the waste. Most pairs are far apart in time. A meeting in the morning can never clash with one in the evening, but the brute force still compares them.
  2. Sort by start. intervals.sort() orders the meetings by start time (ties by end).
  3. Neighbours are enough. Suppose meetings i and j (i before j in sorted order) overlap, so meeting j starts before meeting i ends. Meeting i + 1 starts no later than meeting j, so it also starts before meeting i ends. So whenever some pair overlaps, some adjacent pair overlaps too.
  4. One comparison per neighbour. For each i from 1, if intervals[i][0] < intervals[i - 1][1], the meeting starts before the previous one ends: return False. The strict < lets a meeting start exactly when the previous one ends.
  5. No clash found. If the loop finishes, every adjacent pair is fine, so every pair is: return True.

This is the key idea: sort by start, then any overlap must appear between neighbours.

The key idea

Sort by start and compare each start with the previous end. O(n log n).

Python solution

def can_attend_meetings(intervals):
    intervals.sort()
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False               # starts before the last one ends
    return True

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): every pair is compared onceO(1): two loop indices
Sort and check neighbours (shown code)O(n log n): the sort; the check is O(n)O(1) besides the sort, which works in place (Python's sort may use up to O(n) temporary memory)

Edge cases

  • No meetings ([]): the loop does not run and the answer is True.
  • One meeting: True.
  • Back to back ([[5, 10], [10, 15]]): 10 < 10 is false, so True.
  • Clash with an earlier, longer meeting ([[0, 30], [5, 10], [15, 20]]): 5 < 30 on the first comparison, so False.
  • Unsorted input ([[7, 10], [2, 4]]): sorted to [[2, 4], [7, 10]], then True.
  • Same start time ([[1, 5], [1, 3]]): sorted to [[1, 3], [1, 5]], 1 < 3, so False.
  • The input is changed: sort() reorders the caller's list. Use sorted(intervals) if that matters.

Common mistakes

  • Using <=, which reports back-to-back meetings as a clash.
  • Forgetting to sort, so a clash between meetings that are far apart in the input is missed.
  • Comparing each meeting only with the first one, or tracking only the previous start instead of the previous end.
  • Thinking you must compare with the largest end seen so far. That also works, but it is not needed for a yes or no answer, because the first clash is already between neighbours.
Your turn: a break between meetings

The person now needs at least g minutes between the end of one meeting and the start of the next. Return whether they can attend every meeting. For [[0, 10], [12, 20]] the answer is True with g = 2 and False with g = 3. Describe your approach, then write it if you like.

Compare with our answer

Same sort and neighbour check, with a stricter test: the next start must be at least previous end + g. The neighbour argument still holds, because meeting i + 1 starts no later than any later meeting j.

def can_attend_with_gap(intervals, g):
    ivs = sorted(intervals)
    for prev, cur in zip(ivs, ivs[1:]):
        if cur[0] < prev[1] + g:
            return False
    return True

Time O(n log n), space O(n) for the sorted copy (the caller's list is not changed).

A strong answer mentions: why checking neighbours is still enough with a gap, the exact comparison (< against end + g), and leaving the input unchanged with sorted.

Check what stuck

1. Decide whether a list of 10^5 numbers contains two values that differ by at most d. Which approach fits best?

2. After sorting by start, why is checking adjacent meetings enough?

3. A learner writes <= in the comparison. Which input now gives a wrong answer?

Score 60% or more and the lesson is marked complete.