What single condition tells you two half-open intervals [start, end) overlap?

## The predicate For two ranges `a = [a.start, a.end)` and `b = [b.start, b.end)`, they overlap — share at least one point — exactly when: ``` a.start < b.end and b.start < a.end ``` Two comparisons, one `and`. No case analysis, no sorting, no special handling for containment. ## Derive it, don't memorise it The reliable way to reproduce this under interview pressure is to describe when the ranges **miss**, because missing has only two shapes: - `a` finishes at or before `b` begins: `a.end <= b.start` - `b` finishes at or before `a` begins: `b.end <= a.start` Overlap is the negation of their disjunction. Pushing the negation inward turns the `or` into an `and` and flips each comparison: ``` NOT (a.end <= b.start OR b.end <= a.start) = a.end > b.start AND b.end > a.start = b.start < a.end AND a.start < b.end ``` Which is the predicate above, written the other way round. This derivation is worth saying out loud: it shows the condition is complete, not merely remembered. ## Why enumerating positions goes wrong A very common answer walks through relative positions instead: `a` inside `b`, `b` inside `a`, `a` hanging off the left edge, `a` hanging off the right edge. That is four branches plus the equal-range case, and it is easy to write one of them with the wrong comparison or to forget that identical ranges must count. The negation form absorbs every one of those shapes, including full containment, because containment satisfies both comparisons with room to spare. ## The comparison operator *is* the boundary convention With **half-open** `[start, end)` ranges, the end instant belongs to the *next* range, so touching endpoints do not conflict: an operating room booked 09:00–10:00 leaves 10:00 free, and a 10:00–11:00 request is accepted. That is the behaviour the strict `<` encodes. With **closed** `[start, end]` ranges — or with discrete units where `end` names the last occupied slot — the shared endpoint *is* a conflict, and the predicate becomes `a.start <= b.end and b.start <= a.end`. Both are correct; what is not correct is holding both conventions in one codebase. Nearly every real double-booking bug in a scheduling system traces back to one module treating `end` as exclusive while another treats it as inclusive. Pick half-open — it makes durations subtract cleanly (`end - start`) and makes adjacency free of arithmetic — and write it down where the type is defined. If a domain genuinely needs a gap between bookings — a room needs fifteen minutes of turnover — that belongs in the data, by padding the stored range, not in the predicate. The overlap test should stay the pure geometric question. ## Degenerate and derived quantities A zero-length half-open range `[t, t)` contains no points at all, so under the strict test it overlaps nothing — not even a copy of itself. If an instantaneous event must be able to conflict, model it as a short positive-length range or move to the closed convention deliberately. When two ranges do overlap, their shared portion is `[max(a.start, b.start), min(a.end, b.end))`, and its length is `min(a.end, b.end) - max(a.start, b.start)`. That gives an equivalent phrasing of the whole predicate: **the larger of the two starts is strictly less than the smaller of the two ends**. That form is the one that keeps working when you have a whole collection in hand, and it is worth knowing the one-dimensional fact behind it: for ranges on a line, if every *pair* in a set overlaps, then the whole set shares a common point. That is special to one dimension — it is not true of rectangles or discs — and it is exactly why interval problems are so much friendlier than their two-dimensional cousins. ## Symmetry, ordering, and cost The predicate is symmetric in `a` and `b`, and it assumes nothing about which starts first. A recurring bug is to keep only half of it — `b.start < a.end` — on the grounds that "the list is sorted by start, so `a` comes first". That shortcut is correct only while the precondition holds, and it fails silently the first time a caller hands over unsorted data. Testing the predicate is constant time, but testing *every pair* in a collection is quadratic in the number of ranges. That is perfectly fine for the handful of bookings on one room's day sheet, and it is precisely why the collection-level interval techniques sort first — the pairwise predicate stays the correctness primitive underneath them, but it is not, on its own, an algorithm for a large schedule.