Merge Intervals

Merge intervals combines all overlapping intervals in an unsorted list. Comparing every pair is O(n²) and also awkward, because merging two intervals can create a new overlap with a third. Sorting removes that complication entirely: - Sort by start time, and every interval that can merge with the current one appears immediately next to it — so a single left-to-right pass suffices. After sorting, an interval either overlaps the one being built or begins entirely after it. There is no case where a later interval reaches back to merge with an earlier one. Walk the sorted list keeping a current interval. If the next interval starts at or before the current end, extend the current end to max(currentEnd, nextEnd); otherwise the current interval is finished — append it and start a new one. Taking the maximum of the ends is essential. One interval can fully contain another, as with [1, 10] and [2, 3], and blindly assigning the next interval's end would shrink the merged range. The overlap test must be <=, since touching intervals like [1, 3] and [3, 5] merge into [1, 5] for this problem. The final interval must be appended after the loop, since nothing follows to trigger its append. Omitting that step silently drops the last interval — a bug that only shows in the output's length. Sorting dominates the cost at O(n log n), with the merge pass itself O(n).

Almost every interval problem starts with a sort, and the choice of key is the whole puzzle. Sort by start when you're merging or inserting — it guarantees that anything overlapping the current block appears next, so one pass suffices. Sort by end when you're packing the most non-overlapping items in (the classic greedy scheduling move). If you can't decide, ask what the greedy choice is: merging cares about what begins next, scheduling cares about what frees up soonest.