Double-Booked?
Medium · rating 1400 · Sorting, Greedy
You have n meetings, each with a start and end time. The first line contains n. Each of the next n lines has two integers, the start and end of a meeting (a meeting occupies [start, end)). Print YES if you can attend all of them without overlap, otherwise NO.
Editorial
This problem asks whether a person can attend every meeting with no overlap — a gentle introduction to interval scheduling.
Approach
Sort the meetings by start time. If any meeting begins before the previous one ends, there's a conflict; otherwise they all fit.
intervals.sort()
for i in range(1, len(intervals)):
if intervals[i][0] < intervals[i-1][1]:
return False # overlap
return TrueComplexity
Time: O(n log n) for the sort. Space: O(1) beyond it.
Related problems
- Fit the Most Tasks — Medium
- Matchmaking Gap — Medium
- Shopping on a Budget — Medium
- Minimum Meeting Rooms — Hard
- Job Sequencing — Hard
- Count Anagram Groups — Medium