1447. Merging Only Where the Overlap Has Width

n CLOSED intervals [a, b] are given, every one with a < b so none of them is a single point. Two intervals belong together when the part they SHARE has positive length; sharing a single endpoint is not enough. Belonging together is passed along: if X shares width with Y and Y with Z, all three belong to one group even if X and Z share nothing.

Print the groups, each as the smallest interval containing all of its members, sorted by start.

[1,3] [2,6] [8,10] -> [1,6] [8,10] [1,3] [3,5] [5,9] -> [1,3] [3,5] [5,9] three groups, not one [1,3] [3,5] [2,4] [8,9] -> [1,5] [8,9]

The second and third lines together are the whole problem. In the second, [1,3] and [3,5] share only the point 3, which has no width, so they stay apart, and the same for [3,5] and [5,9]: three groups. In the third the same two intervals are still apart from each other, but [2,4] shares [2,3] with the first and [3,4] with the second, so all three are pulled into one group spanning [1,5].

## What most people try first

The merge from problem 255, which joins intervals whenever a <= end. That rule treats touching as overlapping and answers one group on the second sample where the answer is three. It is the correct rule for a DIFFERENT question, and the only thing separating the two is one character.

The other attempt is to build the graph of which intervals share width and run a union-find over it. That is exactly right and it is O(n^2) to build, 4 * 10^10 pairs at n = 200000.

## One strict comparison

sort by START, ascending run = the first interval for each later interval [a, b]: if a < run.end: STRICT: they share a positive-width piece run.end = max(run.end, b) else: emit run; run = [a, b] emit run

O(n log n).

## Why the strict comparison really is the grouping

Sort by start, and suppose the run so far reaches to run.end. Every member already in the run has a start at or before the new interval's a, because the list is sorted. In particular the member whose end IS run.end starts at or before a, so if a < run.end those two share [a, min(run.end, b)], which has positive width since a < b as well. The new interval therefore belongs to the run.

And if a >= run.end, then every member of the run ends at or before run.end <= a, so the shared part with each of them is at most the single point a. No later interval can repair that either, because every later start is at least a. So the run is complete, and the groups really are the connected components.

## The tie-break, and why it costs nothing here

Sort by start; ties may be broken any way you like. Two intervals with the same start share a piece running from that start to the smaller of their two ends, and since both have positive width, so does that piece. They are therefore always in the same group whichever order they are visited in.

That is a claim about THIS rule, not a general licence. Problem 1478 assigns intervals to groups in sorted order and there the tie-break changes the output, and a version of this problem allowing a == b would break too: a single point sitting inside a long interval shares no width with it, yet the sweep above would swallow it. The constraint a < b is what buys the simple rule.

## Overflow

Coordinates reach 10^9 in magnitude, comfortably inside the 2147483647 a signed 32 bit integer holds, and nothing is summed. The number of groups is at most n, so build the output as one string rather than printing per line.

## Related

Problem 255 merges the same shape of input under the rule that touching counts as overlapping, and is the problem this one is deliberately one character away from. Problem 1463 replaces the strict comparison with a tolerance g, so that intervals within distance g merge; g = 0 there is problem 255's rule and this problem is the case below it.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - each interval is the closed stretch `[a, b]`, and `a < b` so every interval has positive width - two intervals belong together only when the part they share has positive length