Merge two
Put the earlier interval first; if the later one starts inside it, join them into one. About 8 minutes.
Earlier start goes first
Swap the two intervals if needed so that the first starts no later than the second. Now overlap has a single test: does the second begin before the first is over? It is like two shifts, where the one that starts later just has to begin while the earlier one is still on.
This is the same check you wrote before, made simpler by the order.
b starts earlier, so swap: call [1, 6] the first one.
Joining takes the later end
The merged range starts at the first one's start and ends at the later of the two ends. Using the second end alone is the classic slip: with [1, 10] and [2, 3], the merged range is [1, 10], not [1, 3].
A short meeting inside a long one doesn't shorten the long one.
if a[0] > b[0]:
a, b = b, a
if b[0] <= a[1]:
return [[a[0], max(a[1], b[1])]]
return [a, b]What does merging [2, 8] and [1, 3] give?
- A[[1, 8]]
- B[[1, 3]]
- C[[1, 3], [2, 8]]
Show the answer
[[1, 8]]. In order they are [1, 3] then [2, 8]. 2 <= 3, so they join into [1, max(3, 8)] = [1, 8].
Merge two
You are given two intervals a and b, each [start, end] with both ends included. If they overlap, return a list holding the single interval that covers both. If they don't, return both intervals, the one that starts earlier first (if they start together, they overlap).
a = [5, 8], b = [1, 6] → [[1, 8]]
a.length == b.length == 2 · 0 ≤ start ≤ end ≤ 1,000,000,000