Posters on a fence
Posters are pasted along a construction site fence a billion millimetres long, one after another, each new one on top of those already there. A poster occupies the stretch of the fence from millimetre l to millimetre r inclusive, all posters are the same height, so a new poster covers the old ones where they overlap. When the pasters have left, a passer-by counts how many different posters are visible at least a little, by at least one millimetre. Count them too.
Input
The first line holds the number of posters n (1 ≤ n ≤ 100,000). Then n lines l r (1 ≤ l ≤ r ≤ 109) in the order the posters were pasted.
Output
One number: how many posters are visible by at least one millimetre.
Examples
Example 1
3 1 10 1 4 6 10
3
Example 2
3 1 10 1 4 5 10
2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
A fence a billion long cannot be painted millimetre by millimetre. But the posters have only 2n ends. What happens to the fence between two neighbouring ends?
2Hint 2
The first sample: [1, 10], and on top [1, 4] and [6, 10]. If the ends 1, 4, 6, 10 are given ranks 0, 1, 2, 3 and cells are painted from rank l to rank r, the first poster turns out covered. Yet on the fence it is visible. Where did the fifth millimetre go?
3The idea
What must be compressed is not points but elementary segments. A poster [l, r] occupies the half-open interval [l, r + 1). Cut the fence at all points l and r + 1: between neighbouring cuts no poster begins or ends, so each such piece is either entirely under a poster or entirely outside it, and can be treated as one cell. There are at most 2n cells, and painting the cells reproduces painting the fence.
4Walkthrough
Painting the cells in pasting order, overwriting old colours, is possible, but it is O(n · cells) in the worst case, for example when each new poster covers the whole fence. It is handier to go from the end: the last poster is visible where it was put, the one before it where the last did not cover it, and so on. A cell already painted need not be touched again. To jump over painted cells quickly, keep for each cell a link “the next unpainted cell not to the left of me” and compress the paths, as in disjoint set union. A poster is visible if at least one unpainted cell was found in its stretch.
In the second sample [1, 10] is covered entirely: [1, 4] and [5, 10] touch, with no gap between them. The cuts 1, 5, 11 give two cells, both painted by later posters. Compression by ends answers correctly here, which is why this mistake lives long: on many inputs it is invisible.
4+Solution
5Complexity
Sorting the cuts is O(n log n). Each cell is painted once, and jumps along links with path compression add almost nothing: O(n log n) in all.
6Common mistakes
- Compression by ends. The most common mistake, taken apart in the hints. On the very first sample it answers 2 instead of 3.
- Adding points “in between” without care. Sometimes r + 1 or l − 1 are added to the ends, while still working with cells “from rank l to rank r inclusive”. That works too, if done carefully, but it is simpler and safer to switch to half-open intervals [l, r + 1): then a cell is exactly a piece between neighbouring cuts, with no special cases.
- Repainting in forward order. Correct, but quadratic: on a test where each poster is wider than the previous one it paints the same cells a hundred thousand times.