Merge Intervals: Sorting Approach

Sort intervals by start time, then merge greedily:

function mergeIntervals(intervals)
    sort intervals by low endpoint
    result := [intervals[0]]

    for i from 1 to length - 1
        last := result[last index]
        current := intervals[i]

        if current.low <= last.high then
            // Overlapping, merge
            last.high := max(last.high, current.high)
        else
            // Non-overlapping, add new
            result.add(current)

    return result

After sorting, overlapping intervals are adjacent. Merge by extending the high endpoint.

Time: $O(n \log n)$ for sorting. Space: $O(n)$ for result.