914. The Outline of the City

n rectangular buildings stand on a flat ground line. Building i covers the half-open strip [l[i], r[i]) and has height h[i]. Seen from far away they merge into one OUTLINE.

Print the outline as a list of key points. A key point is a position x at which the outline height CHANGES, together with the new height. The last key point always has height 0, where the last building ends.

``` buildings (2,9,10) (3,7,15) (5,12,12) (15,20,10) (19,24,8) -> 2 10 / 3 15 / 7 12 / 12 0 / 15 10 / 20 8 / 24 0

one building (0,1,1) -> 0 1 / 1 0

(0,5,3) and (5,10,3) -> 0 3 / 10 0 ```

The third line is the one to study. Two buildings of the same height sit side by side, so the outline never changes at x = 5 and no key point is emitted there. A key point records a CHANGE, not a building edge.

## What most people try first

Sweeping every integer x and taking the tallest building covering it is O(range * n), and the range here reaches 10^9.

Sweeping only the 2n edge positions and, at each, scanning all n buildings, is O(n^2). At n = 10^5 that is 10^10.

## The method: events plus a heap with lazy deletion

Turn each building into two events and sort them.

at l: a building of height h STARTS and runs until r at r: something ENDS here

Sort by position. At the same position, START events come before END events, and among starts the taller one first. Carry a MAX-heap of (height, right edge) seeded with the sentinel (0, infinity) so it is never empty.

for each distinct position x, in order: push (h, r) for every building starting at x while the top of the heap has right edge <= x: pop it cur = the height at the top of the heap if cur differs from the height last printed: print x and cur

## Lazy deletion, and why it is cheaper than a real delete

When a building ends, its entry is still sitting somewhere inside the heap. Removing it properly means FINDING it, and a binary heap offers no better than a linear scan for that, so an eager delete costs O(n) and the whole sweep becomes O(n^2).

Instead nothing is removed at the moment the building ends. The entry carries its own right edge, so when it eventually reaches the top it can be recognised as expired and dropped then. Each entry is pushed once and popped at most once, so the total extra work over the whole sweep is O(n log n), and the heap is never larger than n + 1.

The heap top may be stale, which is why the popping loop runs BEFORE the height is read, not after.

## Why it is correct

At the moment position x is examined and the expired entries have been dropped, every entry left in the heap belongs to a building with l <= x and r > x, which is exactly the set of buildings covering x under the half-open convention. So the top is the true outline height at x.

Processing every event at the same x together, before reading the height, is what makes the third example come out right: at x = 5 one building ends and another starts, and looking at the heap in between would report a spurious drop to 0.

## The boundary that breaks a careless implementation

The expiry test is right <= x, not <. The strip is half-open, so a building ending at x does not cover x.

Emitting a key point whenever the heap changes, rather than whenever the HEIGHT changes, produces duplicate points at places like x = 5 above. The comparison must be against the last height PRINTED.

The sentinel (0, infinity) is what makes "the ground is at height 0" fall out without a special case. Without it the heap empties between disjoint buildings and reading its top crashes.

## Overflow

Positions and heights both reach 10^9, which fits in a signed 32-bit integer. Nothing here is added or multiplied: the outputs are a position and a height, each taken directly from the input. So 32 bits is genuinely enough, and the only value needing care is the sentinel's right edge, which must be larger than every real position. Use 2 * 10^9 or a 64-bit maximum rather than a value that a real building could reach.

## Related problems

Problem #725 counts how many people are alive in each year with the same event idea and no heap at all, because a COUNT can be maintained by adding and subtracting while a MAXIMUM cannot: when the tallest building ends there is nothing to subtract back to. Problem #170 computes trapped water over a similar silhouette but with a stack, because there the bars are contiguous.

## Cost

Time O(n log n). Space O(n).

Constraints - `1 ≤ n ≤ 100000` - `0 ≤ l < r ≤ 10^9` - `1 ≤ h ≤ 10^9`