Why it works
- The list is sorted and has no overlaps, so it splits into three runs in a row: intervals that end before lo, intervals that overlap the new one, and intervals that start after it. No sort is needed.
- Every overlapping interval widens [lo, hi] with min of the starts and max of the ends. One merged interval replaces them all, so the result has no overlaps.
- Touching counts as overlapping, and the signs say so: end < lo leaves an interval out only if it ends before lo, and start ≤ hi lets [7, 8] in, though it only starts at hi = 7.
Complexity
Time O(n): each interval is looked at once across the three loops. Memory O(n) for the result.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗