Unsorted, every range might overlap any other. Sorted by start, only the one immediately before it can.
ranges = [(5, 8), (1, 3), (2, 6)] # Sorted by start [(1, 3), (2, 6), (5, 8)] # Sweep: compare each with the last one kept # (1, 3) -> keep # (2, 6) -> starts at 2, inside (1, 3), so extend the end to 6 # (5, 8) -> starts at 5, inside (1, 6), so extend the end to 8 # -> [(1, 8)] # The extension is a max(), not an assignment # (1, 10) then (2, 3) must stay (1, 10)
- Sorting turns n-against-n into one pass
Once the ranges are in order of their starts, any range that overlaps the current one must overlap the one immediately before it in the list — so there is nothing to compare against except the last range you kept. That is the whole reason to sort: not tidiness, but reducing the number of comparisons from every pair to one each.
- Extend with max(), never with assignment
When a range is absorbed, the merged end is the larger of the two ends — because a short range can sit entirely inside a long one. Writing `last_end = end` truncates the merged range to the shorter one, which produces gaps that were not there and is invisible on any test where the ranges arrive in increasing size.
- Touching is a decision, not a fact
Does (1, 3) merge with (3, 5)? If these are half-open intervals — a booking from 1 until 3 — then yes, they are continuous. If they are inclusive day ranges, then 3 is in both and they overlap anyway. If they are physical measurements, touching at a point may mean nothing. The code cannot know; the contract has to say, and here it says merge.
Sort by the start first — after that, each range only ever needs comparing with the last one you decided to keep.
Walk the sorted ranges keeping a result list. For each one: if its start is at most the end of the last kept range, they join — replace that last entry with one ending at the larger of the two ends. Otherwise append it as a new range.
`start <= last_end` is what makes touching count; `<` would leave (1, 3) and (3, 5) separate. The merged end must be max(last_end, end), because the incoming range may end sooner than the one it is joining.
def merge_ranges(ranges): for start, end in ranges: if end < start: raise ____(f’range ends before it starts: {(start, end)}') merged = [] for start, end in ____(ranges): if merged and start ____ merged[-1][1]: last_start, last_end = merged[-1] merged[-1] = (last_start, ____(last_end, end)) else: merged.append((start, end)) return merged
def merge_ranges(ranges):
for start, end in ranges:
if end < start:
raise ValueError(
f"range ends before it starts: {(start, end)}"
)
merged = []
# sorted(), not .sort(): the caller's list keeps its own order.
for start, end in sorted(ranges):
# <= rather than <, so ranges that merely touch are joined.
if merged and start <= merged[-1][1]:
last_start, last_end = merged[-1]
# max, because this range may end sooner than the one it joins.
merged[-1] = (last_start, max(last_end, end))
else:
merged.append((start, end))
return merged
Tuples compare element by element, so sorting the pairs orders them by start and breaks ties by end — exactly what the sweep wants, with no key function. It is one of the places where Python’s default tuple ordering is precisely the domain rule rather than a coincidence you should be wary of.
The running merge grows as ranges are absorbed, so the thing to test against is the last entry in the result — which may already reach much further right than the range it started as. Comparing against the previous element of the input instead breaks the chain-of-three case, where the third range overlaps the merged pair but not the original first.
The check loops over all the ranges first, so a bad pair anywhere fails before any work is done — and, more usefully, before the sort, which would otherwise happily order a backwards range into the middle and produce a confident wrong answer. The cost is one extra pass over a list you are about to sort anyway.
If ranges arrive continuously and you need the merged view after each one, rebuilding from scratch each time is quadratic — that is what an interval tree or a sorted container is for, and portion and intervaltree both do this on PyPI with union, intersection and complement already written. If the intervals are dates in a database, the range types in Postgres do it in SQL with an exclusion constraint that can prevent overlapping bookings from existing at all. And be careful applying this to datetimes across a daylight-saving boundary, where two ranges can overlap in wall time and not in real time.
- Return the gaps instead of the merged ranges — the free slots in a calendar — and check that merging your gaps back in reproduces one continuous span.
- Add a parameter deciding whether touching ranges merge, and see which single character it controls.
- Make it work on datetimes as well as numbers, and confirm nothing in the algorithm had to know which it was given.