1441. How Many Whole Positions Are Busy

You are given n intervals over the INTEGERS. Each is CLOSED and written a b, meaning every whole number from a to b inclusive. a may equal b, in which case the interval is the single position a.

Print how many distinct whole positions are covered by at least one interval.

[1,3] [2,6] [9,10] -> 8 1..6 is six positions, 9..10 is two [1,3] [4,7] -> 7 1..7, with no hole between 3 and 4 [5,5] -> 1

The middle line is the one to study. [1,3] and [4,7] do not overlap and do not touch, yet the positions they cover run 1, 2, 3, 4, 5, 6, 7 with nothing missing, because there is no whole number strictly between 3 and 4. Counting positions and measuring length are different questions, and this is where they come apart.

## What most people try first

Marking every covered position in an array. It is correct and it needs an array indexed by coordinate: with a and b reaching 10^9 in both directions that is 2 * 10^9 entries, gigabytes of memory for a problem whose answer is one number.

The second reflex is to reuse the merging rule from problem 1440 unchanged, merging only when a <= end. On [1,3] [4,7] that produces two runs and the count 3 + 4 = 7, which happens to be right, and on [1,3] [5,7] it produces 3 + 3 = 6, which is also right. The rule is only wrong about how many RUNS there are, and since the count is a sum over runs, that does not show up. What does show up is the +1: a run from s to e holds e - s + 1 positions, not e - s.

## Sort, then merge on adjacency

sort by START, ascending run = the first interval total = 0 for each later interval [a, b]: if a <= run.end + 1: it touches or overlaps, so it continues the run run.end = max(run.end, b) else: total += run.end - run.start + 1 run = [a, b] total += run.end - run.start + 1

O(n log n) for the sort and one pass after it.

## Why the + 1 in the merge test is not optional

Two runs that end at e and begin at e + 1 cover a block of positions with no gap, so counting them separately is harmless for the TOTAL but produces a different list of runs. The reason to merge them anyway is that it keeps the invariant honest: after the merge, a run is exactly a maximal block of consecutive covered positions, and that is what the + 1 per run is counting.

Merging with a <= run.end alone and then adding + 1 per run gives the same total on every input, because a split at e | e+1 turns one run of e2 - s + 1 into two runs whose sizes still add to e2 - s + 1. Convince yourself of that before deciding which rule to write; the block ahead has problems where the run count IS the answer.

## The boundary that breaks a careless implementation

a == b is a legal interval covering exactly one position, so the answer for [5,5] is 1 and not 0. A solution that computes b - a reports 0 for it, and reports 2 * 10^9 rather than 2000000001 for the widest interval allowed.

## Overflow

The largest possible answer is every position from -10^9 to 10^9, which is 2000000001. A signed 32 bit integer holds 2147483647, so that FITS, by about 147 million. It is worth noticing how narrow that margin is: one more order of magnitude on the coordinate range and it would not.

## Related

Problem 1440 measures the LENGTH of the union of half-open intervals; this one COUNTS whole positions under closed intervals, and the two differ by exactly one per run. Problem 255 merges closed intervals and prints the list. Problem 1442 asks how many positions are covered exactly once, which no merging rule can answer.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each interval is the closed range `[a, b]` over the integers, so `a == b` covers exactly one position - intervals arrive in no particular order and may overlap freely