Sort intervals by start before merging

After sorting intervals by start, keep the current merged interval. If the next interval starts before or at its end, extend the end to the larger endpoint; otherwise, save the current interval and start a new one. Sorting costs O(n log n), and the scan is O(n). This assumes closed intervals; for half-open intervals, decide whether touching endpoints should merge.