14. Merge Intervals

Given n intervals as (start, end) pairs, merge all overlapping intervals (two intervals that touch at an endpoint also count as overlapping). Print the merged intervals, one per line, each as 'start end', in ascending order of start.

Input: The first line contains n, the number of intervals. Each of the next n lines contains two integers, start and end, describing one interval. Output: Print the merged intervals, one per line, each as 'start end', in ascending order of start.

1 <= n <= 10^5

Sorting by START value (not end value) is the crucial first step that makes a single linear pass sufficient - without sorting, you'd need to compare against every previous interval, not just the most recent one.

Given a bunch of time ranges that might overlap, combine any that touch or overlap into single, bigger ranges. Brute force: Compare every pair of intervals directly to check for overlap, merging as you find them, and repeat until no more merges are possible - this can work but is much less efficient (potentially O(n²) or worse) than a single sorted pass. Optimised: Sorting by start value FIRST means any interval that could possibly overlap with your current merged interval must appear immediately next in the sorted order - so a single left-to-right pass, extending or finalizing the current merge as you go, correctly handles every overlap without ever needing to look back or compare non-adjacent intervals.

Treat each interval as a node, and draw an edge between any two intervals that overlap (checked pairwise). Then find the connected components of this graph using DFS, BFS, or union-find, and merge all intervals within each connected component into a single combined interval (taking the minimum start and maximum end across the component). This correctly groups together intervals that overlap transitively (even if not directly with each other) via a different technique - explicit component-finding rather than sequential scanning - though building the overlap graph itself still requires checking many pairs of intervals. Time: O(n^2) Space: O(n)

Repeatedly scan through the entire (shrinking) list of intervals looking for any two that overlap; whenever a pair is found, merge them into one combined interval and restart scanning from the beginning of the list. Continue this process until a full pass finds no more overlapping pairs to merge. This is correct because it keeps merging until no more merges are possible, but restarting the scan after every single merge and having no ordering to exploit makes it slow, especially when many intervals need merging in sequence. Time: O(n^2) or worse Space: O(n)

Sort all intervals by their start value, then make a single pass through them while maintaining a 'current merged interval'. For each next interval in sorted order, if it overlaps with (or touches) the current merged interval, extend the current interval's end to cover it; otherwise, output the current merged interval and start a new one from this interval. Sorting first guarantees that any interval overlapping the current one must appear immediately in this sorted sequence, so a single linear sweep after the sort is enough to correctly merge everything, avoiding the graph-building or repeated-rescanning overhead of the other two approaches. Time: O(n log n) Space: O(n)

1. Sort all the intervals by their START value. 2. Walk through them in order, keeping a 'current merged interval' you're building up. 3. If the next interval's start is within (or touching) the current merged interval's end, extend the current merged interval's end if needed. 4. If the next interval starts AFTER the current merged interval fully ends, the current merged interval is finished - record it, and start a new one with this next interval.

Time: O(n log n), dominated by the initial sort - the merging pass itself afterward is a single linear scan. Space: O(n), for the sorted list and the resulting merged intervals.

n = 1 (a single interval, nothing to merge); intervals that only touch at an endpoint (must still merge per the stated rule); fully disjoint intervals staying separate, as in the example; and n = 10^5 (largest, confirming a sort-then-sweep approach is O(n log n)).

Be explicit that two intervals touching exactly at an endpoint (like [1,3] and [3,5]) still count as overlapping per this problem's own rule - a common ambiguity interviewers deliberately probe.