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 True

Complexity

Time: O(n log n) for the sort. Space: O(1) beyond it.

Open Double-Booked? in Code Arena →