1453. Every Change in the Load

n sessions are given. Session i is open over the HALF-OPEN stretch [a, b) with a < b, so a session closing at t and one opening at t are never open together.

The LOAD at a moment is how many sessions are open at it. It starts at 0 before the first opening and returns to 0 after the last closing. Print every moment at which the load CHANGES, together with the load from that moment on.

[1,5) [2,6) [8,9) -> 1 1 / 2 2 / 5 1 / 6 0 / 8 1 / 9 0 [1,3) [3,5) -> 1 1 / 5 0 [1,4) [1,4) [5,8) [5,8) -> 1 2 / 4 0 / 5 2 / 8 0

The second line is the whole difficulty. The two sessions merely TOUCH at moment 3: one closes and the other opens there, so the load goes 1, then 0 for no time at all, then 1 again. The load at moment 3 is 1, exactly what it was just before, so nothing CHANGED there and no line is printed for it. A change point records a change, not an endpoint.

## What most people try first

Printing one line per endpoint, which is 2n lines and reports moment 3 in the second sample with load 1 next to the load 1 it already had. Any reader reconstructing the load from that output gets the right function, so it feels harmless, and it is wrong because the output is defined as the changes.

The second reflex is a counter per moment, which needs 2 * 10^9 entries because coordinates reach 10^9 in both directions.

## Sweep, and emit only when the level moves

events: (a, +1) and (b, -1) for every session; sort by coordinate level = 0; previous = 0 for each distinct coordinate x, in order: apply EVERY event at x if level != previous: emit (x, level) previous = level

O(n log n) for the sort, then one pass. The output holds at most 2n lines and often far fewer.

## Why every event at a coordinate must be applied before emitting

Suppose three sessions close at 7 and two open at 7. Applying them one at a time and emitting after each produces five lines at moment 7, four of which describe loads that hold for no time whatsoever. Grouping them gives one line at 7 whose level is the load that actually holds from 7 onwards, which is what the question asks for. And if the closings and openings happen to cancel, the group produces no line at all, which is the second sample.

This also makes the tie-break between a close and an open at the same coordinate irrelevant, since they are applied together. That is a different situation from problem 1448, where the running count is read after every single event and the tie-break decides the answer.

## The boundary that breaks a careless implementation

The first emitted line always has a level of at least 1, because the sweep starts from previous = 0 and the first coordinate is an opening. The last emitted line always has level 0, at the largest end coordinate. A solution that stops emitting once the level reaches 0, or that never emits the final drop, loses the right-hand edge of the picture.

The sessions also need not be sorted on input, and a solution that walks them in the given order produces a jumbled set of change points.

## Overflow

Levels are at most n = 200000 and coordinates at most 10^9 in magnitude, both inside the 2147483647 a signed 32 bit integer holds. Nothing is summed. The output can reach 2 * 10^5 lines, so build it as one string rather than printing inside the loop.

## Related

Problem 914 builds the skyline of buildings, where the value at a point is the MAXIMUM height covering it and a heap is needed to retract a building that is no longer the tallest. Here the value is a COUNT, which is additive, so a running total replaces the heap entirely and the problem becomes a sweep rather than a structure. Both suppress a key point where the value does not change, and in both that is where the marks are lost.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - each session is open over the half-open stretch `[a, b)`, so closing at `t` and opening at `t` do not overlap - sessions arrive in no particular order and may repeat