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
- 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.
- Sort by start.
intervals.sort()orders the meetings by start time (ties by end). - 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.
- 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: returnFalse. The strict<lets a meeting start exactly when the previous one ends. - 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 TrueIn 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
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every pair is compared once | O(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 isTrue. - One meeting:
True. - Back to back (
[[5, 10], [10, 15]]):10 < 10is false, soTrue. - Clash with an earlier, longer meeting (
[[0, 30], [5, 10], [15, 20]]):5 < 30on the first comparison, soFalse. - Unsorted input (
[[7, 10], [2, 4]]): sorted to[[2, 4], [7, 10]], thenTrue. - Same start time (
[[1, 5], [1, 3]]): sorted to[[1, 3], [1, 5]],1 < 3, soFalse. - The input is changed:
sort()reorders the caller's list. Usesorted(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.
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.
1. Decide whether a list of 10^5 numbers contains two values that differ by at most d. Which approach fits best?
After sorting, the closest partner of any number is a neighbour, the same argument as for meetings: O(n log n). A set only finds exact differences, all pairs is O(n²), and the unsorted order says nothing about closeness.
2. After sorting by start, why is checking adjacent meetings enough?
If meeting i overlaps a later meeting j, then meeting i + 1 starts no later than j and so also before i ends. The overlapping pair itself need not be adjacent: in [[0, 30], [5, 10], [15, 20]], [0, 30] and [15, 20] overlap with a meeting between them.
3. A learner writes <= in the comparison. Which input now gives a wrong answer?
With <=, the meeting starting at 10 counts as clashing with the one ending at 10, so the code returns False. None of the other inputs has a meeting that starts exactly when the previous one ends.
Score 60% or more and the lesson is marked complete.