1442. The Positions Only One Booking Wants

You are given n CLOSED intervals over the integers, written a b and covering every whole position from a to b inclusive, with a <= b.

Print how many whole positions are covered by EXACTLY ONE of them.

[1,4] [3,6] [9,10] -> 6 1,2 and 5,6 and 9,10 [1,5] [1,5] -> 0 every position is wanted twice [1,3] [3,6] -> 5 only position 3 is shared

The third line is the one this topic keeps returning to. [1,3] and [3,6] merely TOUCH at position 3, and because the intervals are closed both contain it, so it is covered twice. Positions 1, 2, 4, 5, 6 are covered once, which is five. Under a HALF-OPEN reading of the same two pairs there would be no shared position at all and the answer would be 6. The convention is not decoration; it is the answer.

## What most people try first

Merging the intervals, as problems 1440 and 1441 do, and then measuring. That throws away exactly the information being asked for: merging records WHETHER a position is covered and forgets HOW OFTEN. On [1,5] [1,5] the merge gives one run of five positions and the answer is 0.

The second reflex is an array of counters indexed by position. It is correct and it needs 2 * 10^9 entries, because coordinates run to 10^9 in both directions.

## Count the changes, not the positions

Nothing about a position matters except how the count changes as you walk left to right, and the count changes only at 2n places:

for each interval [a, b]: event(a, +1) and event(b + 1, -1) sort the events by coordinate walk them, applying EVERY event at a coordinate before looking at the gap: after the events at x, the count holds for all positions x .. next - 1 if that count is 1: answer += next - x

The b + 1 is what makes a CLOSED interval into a half-open one internally: the count drops just after b, not at b. Sorting the 2n events costs O(n log n), about 7 * 10^6 comparisons at n = 200000, and the walk is one pass.

## Why all events at one coordinate must be applied together

Suppose one interval ends at 7 and another begins at 7. The events are (8, -1) and (7, +1), so they land at different coordinates and nothing goes wrong. Now suppose two intervals both begin at 7 and a third ends at 6. The events (7, +1), (7, +1) and (7, -1) all sit at 7, and reading the count between them would report a level that holds over no positions at all. Applying every event at a coordinate first, and only then measuring to the next coordinate, makes the level you read the level that actually holds there.

This also means the tie-break between a +1 and a -1 at the same coordinate is irrelevant HERE, because they are applied as a group. In the sweeps ahead, where the level is read after each single event, it decides the answer.

## Overflow

The answer is at most every position from -10^9 to 10^9, which is 2000000001, and a signed 32 bit integer holds 2147483647, so it FITS. The event coordinate b + 1 reaches 1000000001, which also fits. The accumulating answer is safest in 64 bit anyway.

## Related

Problem 1441 counts positions covered at least once and can be answered by merging. This one cannot, which is the point. Problem 723 asks whether every position in a window is covered, over an axis bounded by 2000 so a plain difference array fits; here the axis is 2 * 10^9 wide and the events have to carry their own coordinates. Problem 1461 asks for the widest stretch at a given level rather than the total.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a ≤ b ≤ 10^9` - each interval is the closed range `[a, b]` over the integers, so a position on either endpoint is covered - intervals arrive in no particular order and may repeat