How to Check if Two Intervals Overlap, and Why Sort by Start

Every interval problem, from merging meetings to booking rooms, rests on one small question: do these two ranges overlap? Most people answer it with four nested cases ("starts inside", "ends inside", "contains", "is contained") and a bug in one of them. There is a one-line test with no cases at all, and once you have it, sorting by start turns the question about a whole list into a single left-to-right scan.

The problem it solves

An interval is a pair, (start, end): a meeting, a reservation, a span of memory, a range of IDs. You need to know:

• Do two given intervals overlap, and if so, where?
• Does any pair in a list overlap: can one person attend every meeting?
• Which interval is the first clash in a calendar?

Comparing every pair answers the list questions in O(n²). With sorting, they cost O(n log n), and the sort is the only expensive part.

The intuition

Think about when two intervals do not overlap. Either a ends before b starts, or b ends before a starts. That is the complete list of ways to be apart. Negate it and you get the overlap test:

• a overlaps b exactly when a.start < b.end and b.start < a.end.

Each one must begin before the other finishes. Containment, partial overlap and identical intervals all satisfy it; nothing else does. No special cases.

Whether touching counts is a decision, not a detail. With half-open intervals, [start, end), a meeting from 9 to 10 and one from 10 to 11 do not clash: the first is over the instant the second begins. That is the usual model for time and the one most interview problems use, and it is the strict <. With closed intervals, where both endpoints belong, sharing an endpoint is an overlap and the test becomes <=. Ask which one the problem means before you write the comparison.

The overlap itself, when there is one, runs from the later start to the earlier end: (max(a.start, b.start), min(a.end, b.end)). If that range is empty, there is no overlap, which gives a second, equivalent test.

Now a whole list. Sort by start. Every interval after the one you are holding starts at or after it, so if any two intervals clash, two neighbours in sorted order clash. The reason: if interval i overlaps a later interval j, then j starts before i ends, and the interval right after i starts no later than j, so it also starts before i ends. One scan comparing each interval with the next is enough to answer "can I attend everything?".

Python sorts tuples by start, then by end for ties, so a plain sorted(intervals) is the sort you want.

Watch it run

The animation draws the lesson's four meetings in the order they were booked, each just a start and an end. It takes 9–10 and 9–12 first: each begins before the other finishes, so they overlap. Then 9–10 and 11–14 fail the same test, because 11 is not before 10, so there is clear air between them. Asking that of every pair costs n squared comparisons, and most of them are answered by the picture. So the meetings are sorted by start instead: 9–12 moves up and 13–15 drops to the bottom, giving 9–10, 9–12, 11–14, 13–15, with starts that only move to the right as you read down. A dashed scan line then sweeps left to right, and a single pass is enough because whatever comes next starts at or after what you are holding. One sort, one scan: the shape of nearly every interval problem.

The code

The overlap test in both conventions, the intersection, and the sorted scan that finds the first clash:

def overlap(a, b):
    return a[0] < b[1] and b[0] < a[1]          # half-open: touching ends do not count

def overlap_closed(a, b):
    return a[0] <= b[1] and b[0] <= a[1]        # closed: a shared endpoint counts

def intersection(a, b):
    lo, hi = max(a[0], b[0]), min(a[1], b[1])   # latest start, earliest end
    return (lo, hi) if lo < hi else None

print(overlap((9, 10), (9, 12)), overlap((9, 10), (11, 14)))         # True False
print(overlap((9, 10), (10, 11)), overlap_closed((9, 10), (10, 11))) # False True
print(intersection((9, 12), (11, 14)), intersection((9, 10), (11, 14)))  # (11, 12) None

meetings = [(9, 10), (13, 15), (9, 12), (11, 14)]
print(sorted(meetings))            # [(9, 10), (9, 12), (11, 14), (13, 15)]

def first_clash(intervals):
    """Sorted by start, a clash anywhere means a clash between neighbours."""
    s = sorted(intervals)
    for prev, cur in zip(s, s[1:]):
        if cur[0] < prev[1]:
            return prev, cur
    return None

def can_attend_all(intervals):
    return first_clash(intervals) is None

print(first_clash(meetings))                                  # ((9, 10), (9, 12))
print(can_attend_all(meetings), can_attend_all([(13, 15), (9, 10), (10, 11)]))  # False True

The neighbour argument is the claim most worth distrusting, so it is checked against every pair. The overlap tests and the intersection are checked against a brute force that lists the integer instants each interval covers, on 3,000 seeded random cases:

import random
from itertools import combinations

def points(a, closed=False):
    """Brute force: the integer instants an interval covers."""
    return set(range(a[0], a[1] + (1 if closed else 0)))

def rand_interval(rng):
    s = rng.randint(0, 20)
    return (s, s + rng.randint(1, 8))           # start < end

rng = random.Random(33)
ok = True
for _ in range(3_000):
    a, b = rand_interval(rng), rand_interval(rng)
    ok &= overlap(a, b) == bool(points(a) & points(b))
    ok &= overlap_closed(a, b) == bool(points(a, True) & points(b, True))
    cut = intersection(a, b)
    ok &= (cut[1] - cut[0] if cut else 0) == len(points(a) & points(b))
    day = [rand_interval(rng) for _ in range(rng.randint(0, 8))]
    ok &= can_attend_all(day) == (not any(overlap(x, y) for x, y in combinations(day, 2)))
print(ok)                                       # True

The complexity

• Overlap test and intersection: O(1).
• Any overlap in a list, by pairs: O(n²) time, O(1) space.
• Any overlap, sort then scan: O(n log n) time for the sort plus O(n) for the scan; O(n) space for the sorted copy, or O(1) extra if you sort in place.
• The patterns cheat sheet groups this with merge, insert and meeting rooms under one sort-then-sweep pattern.

Where it goes wrong

• Writing four cases. "Starts inside or ends inside" misses containment; the two-comparison test covers everything.
• Mixing conventions. < versus <= decides whether 9–10 and 10–11 clash. Pick one on purpose.
• Comparing only neighbours without sorting. The neighbour argument needs start order.
• Stopping at neighbours when you need every clash. Neighbours prove that some overlap exists; counting all overlapping pairs or merging needs the largest end seen so far, not just the previous interval's end.
• Sorting by end when the problem needs start. Sorting by end is the right move for a different question: the greedy maximum set of non-overlapping intervals.

When it shows up in interviews

Directly as "meeting rooms" (can one person attend all meetings?) and "do these two rectangles overlap?", which is the same test on each axis. Indirectly in every larger interval problem: merge intervals, insert interval, meeting rooms II and interval scheduling, where sorting by end replaces sorting by start. A wrong overlap test in the first minutes quietly breaks everything built on it.

How to say it in an interview

"Two intervals overlap when each starts before the other ends: a start below b end, and b start below a end. That's the negation of the only two ways to be apart, so it covers containment with no special cases. I'd confirm whether touching endpoints count, which decides strict or non-strict comparison. For a list, I sort by start, then compare each interval with the next: if any pair overlaps, some adjacent pair does. That's O(n log n) for the sort and a linear scan."