1463. Merging Anything Close Enough

n CLOSED intervals [a, b] are given with a <= b, so a single point is allowed. A tolerance g is also given. Two intervals belong to the same group when the GAP between them is at most g, where the gap between [a1, b1] and [a2, b2] is max(a1, a2) - min(b1, b2) and is taken as 0 when they overlap. Belonging is passed along, so a third interval can bridge two that are far apart.

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

g = 2, [1,3] [6,8] [12,14] [20,21] -> [1,3] [6,8] [12,14] [20,21] g = 0, [1,3] [3,5] [6,9] -> [1,5] [6,9] g = 2, [1,10] [3,4] [11,12] -> [1,12]

The first line has gaps of 3, 4 and 6, all larger than the tolerance of 2, so nothing merges. The second line has g = 0, which is the ordinary rule where touching merges and a gap of even one unit does not. The third line is the transitive case: [1,10] and [11,12] are a gap of 1 apart, which is within the tolerance, so they join even though [3,4] is irrelevant to that decision.

g = 0 is exactly the rule problem 255 uses, and this problem is that problem with the rule turned into a parameter.

## What most people try first

Building the graph of which intervals are close enough and running a union-find over it. That is correct and O(n^2) to build, which is 4 * 10^10 pairs at n = 200000.

The second reflex is to merge only intervals that are ADJACENT after sorting, in one pass, without keeping a running end. On [1,10] [3,4] [11,12] that compares [3,4] with [11,12], a gap of 7, and reports three groups.

## Sort, then extend a run while the gap allows

sort by START, ascending run = the first interval for each later interval [a, b]: if a <= run.end + g: close enough, it joins run.end = max(run.end, b) else: emit run; run = [a, b] emit run

O(n log n).

## Why comparing against the RUN and not the previous interval is correct

Sort by start. Every member already in the run has a start at or before the new interval's a, so the member whose end is run.end also starts at or before a. The gap between that member and the new interval is therefore a - run.end, which is at most g exactly when a <= run.end + g. So the test decides membership against a real member of the run.

Going the other way: if a > run.end + g then every member ends at or before run.end, so its gap to the new interval is at least a - run.end > g, and the same holds for every interval still to come since their starts are at least a. So the run really is finished.

Keeping run.end as a running MAXIMUM is what makes this work. The previous interval in sorted order may be nested deep inside the run and end far to the left, which is the third sample.

## The boundary that breaks a careless implementation

The test is a <= run.end + g, non-strict. With g = 0 that is a <= run.end, which merges touching intervals, matching problem 255. Making it strict turns it into problem 1447's rule, where touching intervals stay apart.

a == b is legal and means a single point. A point at distance exactly g from a run joins it.

## Overflow

run.end + g reaches 10^9 + 10^9 = 2 * 10^9. A signed 32 bit integer holds 2147483647, so that FITS, with about 147 million to spare. It is the only arithmetic in the problem and it is worth doing in 64 bit anyway, since a tolerance one order of magnitude larger would break it.

## Related

Problem 255 is this problem at g = 0 and prints the same shape of output. Problem 1447 is the rule one step below, where intervals must share positive width to merge at all, so the three problems form a ladder: share width, touch, or come within g.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ g ≤ 10^9` - `-10^9 ≤ a ≤ b ≤ 10^9`, so `a == b` is a single point - each interval is the closed stretch `[a, b]` - two intervals are in the same group when the gap between them is at most `g`, and this is passed along through other intervals