Overlapping Intervals

Merge Intervals was about combining overlapping ranges into clean ones. This pattern is its close cousin with a different question: not "what do these ranges add up to" but "do any of them clash, and can everything coexist." Conflict detection, in other words. It shows up any time a single resource, a room, a machine, a frequency band, can only host one thing at a time, and you need to know whether a set of demands fits.

The primitive underneath is worth memorizing because it is easy to get backwards. Two intervals a and b overlap exactly when each starts before the other ends: a.start < b.end and b.start < a.end. That is the whole test. Everything else is about applying it to a whole set without checking all n^2 pairs.

The overlap test, and why sorting scales it

Comparing every interval to every other is quadratic, but sorting rescues you the same way it did for merging. Sort by start time, and any conflict must involve neighbors, because once the list is ordered, the only interval that can clash with the current one is the one just before it. So a single pass answers "does anything conflict here."

def has_conflict(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:   # starts before the previous ends
            return True
    return False

On [[1, 3], [2, 4], [5, 6]] the pair [1,3] and [2,4] trips the test and it returns True. The sort costs O(n log n) and the scan is linear. This is the bones of the classic "can this person attend all their meetings" question: any overlap at all and the answer is no.

The intervals 1-3, 2-4 and 5-6 sorted by start; 2-4 begins at 2, before 1-3 ends at 3, so the two overlap and conflict, while 5-6 starts after everything and is clear, a clash found by scanning only adjacent intervals.

In the wild: admission control in a booking system

A reservation service faces this constantly. Someone requests a room from 2 to 4; before confirming, the service must know whether that window collides with any existing booking. For a batch of requests validated together, the sort-and-scan above answers it directly. But a live service does not get the whole set at once, it gets one request at a time against a growing calendar, and re-sorting on every request would be wasteful.

The same overlap test still drives it, now backed by a structure built for repeated queries. Keep existing bookings in an interval tree, and a new request checks for a clash in O(log n):

def conflicts_with_any(new, tree):
    # tree.overlaps(interval) walks the interval tree, returning True on the first clash
    return tree.overlaps(new)     # each node stores the max end in its subtree to prune

It is the same class of problem as attending all your meetings, scaled to a service: the question is always "does this range overlap any of those." What changes is only how often you ask. Ask once about a fixed set and you sort and scan; ask continuously against a changing set and you pay for a structure that keeps the overlap test cheap. The overlap primitive never moves.

The trigger

A single resource that can host one thing at a time, and a question about clashes, feasibility, or "can all of these coexist." The tell is the word conflict, or a constraint that two things cannot happen at once. Reach for the overlap test, and sort to make it a neighbors-only scan.

Where it shows up

  • Feasibility checks: can one person or one room serve this whole schedule without a clash.
  • Admission control: does a new reservation, lock, or bandwidth request collide with what is already granted.
  • Relationship queries: which existing intervals contain a point, or overlap a given range.

Where it bites

The boundary convention is the usual culprit: is a booking that ends at 3 in conflict with one that starts at 3? Inclusive versus exclusive ends flips the answer, so < versus <= must be a deliberate choice tied to the domain. And as always, sorting by the wrong key, end instead of start, breaks the neighbors-only guarantee that makes the linear scan valid.

When it is the wrong tool

If you actually want the merged ranges rather than a yes or no, this is the wrong stopping point; go all the way to Merge Intervals. If the question is how many overlap at once, not merely whether any do, a boolean scan will not tell you, and you want a sweep line counting concurrency. And for a set that changes constantly, re-sorting per query is the wrong reflex: build an interval tree or a segment tree once and let it absorb the churn.

Its neighbors

It shares its entire foundation with Sorting-Based Patterns and is one comparison away from Merge Intervals, which picks up where detection ends. When the follow-up becomes "keep the largest conflict-free subset," you cross into the Greedy activity-selection problem, and when it becomes "how many at once," into the sorting sweep line.

References