Attend Every Meeting
Problem
A calendar lists meetings as [start, end] pairs in no particular order. Decide whether one person can sit through every meeting from start to finish. A meeting that ends exactly when another begins is fine, because the person can walk straight from one to the next.
Examples
Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: False
Why: the long meeting swallows both of the othersInput: meetings = [[7, 10], [2, 4], [4, 7]]
Output: True
Why: in time order the meetings only touch at their endsInput: meetings = []
Output: True
Why: edge case, an empty calendar has nothing to clashHints
0 / 3
Comparing every pair of meetings works but is quadratic. Think about which pairs can actually clash once you look at them in a sensible order.
After sorting by start time, a meeting can only collide with something that starts before it, and the one most likely to still be running is the one directly before it.
Sort by start time and walk the list once. If any meeting starts before the previous meeting ends, return False. If the walk finishes, return True.
Solution
Once the meetings are sorted by start time, the only way two of them can overlap is for some meeting to begin before its immediate predecessor ends: if neighbours in that order never overlap, their end times are also in order, so nothing further back can reach forward past them. That turns a pairwise question into one comparison per adjacent pair, with a strict less-than so that touching meetings pass. Time is O(n log n) for the sort, and space is O(n) for the sorted copy.
def can_attend_all(meetings):
ordered = sorted(meetings) # by start time
for prev, cur in zip(ordered, ordered[1:]):
if cur[0] < prev[1]: # starts before the last one ends
return False
return True
print(can_attend_all([[0, 30], [5, 10], [15, 20]])) # -> False
print(can_attend_all([[7, 10], [2, 4], [4, 7]])) # -> True
print(can_attend_all([])) # -> TrueStuck on the idea rather than the code? Meeting Rooms covers it.