Interval Basics & Sorting

The Idea

An interval is just a pair: start and end. Two of them overlap when each begins before the other finishes — one test, no special cases.

Checking every pair costs n squared. Sorting by start costs n log n and then guarantees something useful: every interval you meet next starts at or after the one you are holding.

Real-World Example

A shared calendar drawn left to right across the day. Nobody compares Tuesday's fourth meeting with its first — the clashes are visible because the bars are laid out in time order, which is exactly what sorting by start does.

The Code

meetings = [(9, 10), (13, 15), (9, 12), (11, 14)]
meetings.sort()                          # by start, ties broken by end
def overlap(a, b):
    return a[0] < b[1] and b[0] < a[1]   # touching ends do not count

print(meetings)
print(overlap(meetings[0], meetings[1]), overlap(meetings[0], meetings[2]))

spans = [(5, 8), (1, 4), (1, 2)]
spans.sort()
print(spans[0])