When do two intervals conflict?

Get the overlap test exactly right, including whether touching counts, and most of this unit follows.

Key idea

Two intervals overlap when neither ends before the other starts

It is easier to say when they do not overlap: one finishes before the other begins. Everything else is an overlap.

So for intervals [a1, b1] and [a2, b2], they overlap when a1 < b2 and a2 < b1. Writing it as the negation of the simple case is far more reliable than trying to enumerate the ways two intervals can sit against each other, of which there are six.

1def overlaps(first, second):2    a1, b1 = first3    a2, b2 = second4    return a1 < b2 and a2 < b15 6print(overlaps([1, 4], [3, 6]))     # genuine overlap7print(overlaps([1, 4], [4, 6]))     # touching at 48print(overlaps([1, 4], [5, 6]))     # separate

Why it works

Sorting by start makes the test local

Comparing every pair is O(n squared). Sort by start time and something useful becomes true: if an interval overlaps anything earlier, it overlaps the one immediately before it in sorted order, or an even earlier one that reaches further.

For the simplest question, does any pair conflict, sorting by start means one linear pass comparing each interval to its predecessor is enough.

1intervals = [[7, 10], [2, 4], [3, 6]]2ordered = sorted(intervals)              # by start, then by end3print("sorted:", ordered)4 5earlier, later = ordered[0], ordered[1]6print(f"{earlier} and {later} conflict:", later[0] < earlier[1])

Once sorted, a comparison against the immediate predecessor is the only one worth making.

The shape of every problem here

Sort by start or by end. Make one pass. Compare each interval against something you are carrying: the previous interval, the current merged block, the last end you accepted.

The problem below is the smallest version: sort by start, and check whether any interval begins before its predecessor finishes.

Predict the output· 5 min

Predict the output: strict versus non-strict

Two overlap tests differing only in strictness, applied to intervals that touch. Type the two values separated by a space.

Python

1def overlaps_strict(first, second):2    return first[0] < second[1] and second[0] < first[1]3 4def overlaps_closed(first, second):5    return first[0] <= second[1] and second[0] <= first[1]6 7print(overlaps_strict([1, 4], [4, 6]), overlaps_closed([1, 4], [4, 6]))

Printed output

Problem· 14 min

Meeting Rooms

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

The shape of every problem here

Sort by start or by end. Make one pass. Compare each interval against something you are carrying: the previous interval, the current merged block, the last end you accepted.

The problem below is the smallest version: sort by start, and check whether any interval begins before its predecessor finishes.

1def overlaps_strict(first, second):2 return first[0] < second[1] and second[0] < first[1]3 4def overlaps_closed(first, second):5 return first[0] <= second[1] and second[0] <= first[1]6 7print(overlaps_strict([1, 4], [4, 6]), overlaps_closed([1, 4], [4, 6]))