Merge Overlapping Intervals

You are given a collection of n intervals, each described by a start and an end value. Merge all overlapping intervals and return the resulting set of non-overlapping intervals, sorted by start value. Two intervals that only touch at a single point (one interval's end equals another's start) must also be merged into one.

Input: The first line contains an integer n, the number of intervals. Each of the next n lines contains two integers, start and end, for one interval. Output: Print m, the number of merged intervals, on the first line, followed by m lines each containing the start and end of a merged interval, sorted by start.

1 <= n <= 8000 0 <= start <= end <= 10^9 for every interval

Sorting by START value (not end value) is the crucial first step that makes the entire single-pass sweep technique valid - this is a foundational pattern reused across many interval-based problems.

Merge a collection of overlapping time intervals into the smallest possible set of non-overlapping intervals. Brute force: Compare every pair of intervals directly, merging any that overlap, and repeat until no more merges are possible - this costs O(n²) or worse, unnecessary once the intervals are sorted. Optimised: Sorting by START value FIRST guarantees that any two intervals that could possibly overlap become ADJACENT in the sorted order - a single linear sweep, extending or closing off the current merged interval as needed, then finds all merges in one pass, with no need to ever re-compare non-adjacent intervals.

1. Sort the intervals by their START value first - overlaps can only occur between intervals that become ADJACENT after this sort. 2. Sweep through the sorted intervals, keeping a running 'current merged interval'. 3. Extend the current merged interval's end whenever the next interval's start does NOT come strictly after it (including when they just TOUCH); otherwise, close off the current merged interval and start a new one.

Time: O(n log n), dominated by the initial sort - the sweep itself is a single O(n) pass. Space: O(n), for the resulting merged intervals list.

No two intervals may overlap at all (the output is just the input resorted by start), or every interval could merge into a single interval.

Be precise about the TOUCHING-endpoints rule explicitly stated in this problem (end == next start still counts as overlapping and must be merged) - a common detail that's easy to get wrong if using a strict '<' instead of '<=' comparison.