Merging intervals starts with sorting

For closed intervals, sort by start, then scan from left to right. If the next interval starts at or before the current end, extend the current interval; otherwise, emit it and start a new one. Sorting takes O(n log n), and the scan takes O(n). For half-open intervals, the overlap condition differs at equal endpoints.