The tell: Overlapping ranges to combine — sorting makes overlaps adjacent.
How you get there
1Sort by start so any overlap is with the immediately preceding interval.
2If the next start is at or before the current end, extend the end.
3Extend to the maximum of the two ends, not simply the newer one.
Solution
Python
def merge(intervals: list[list[int]]) -> list[list[int]]:
intervals.sort(key=lambda pair: pair[0])
out: list[list[int]] = []
for start, end in intervals:
if out and start <= out[-1][1]:
out[-1][1] = max(out[-1][1], end) # max, not end
else:
out.append([start, end])
return out
Time
O(n log n)
Space
O(n)
What goes wrong
Setting the merged end to `end` truncates when a shorter interval is fully contained in a longer one.