Easy Skyline
Time limit2sMemory limit128 MB
Given the sequence of skyline breakpoints, find the minimum number of axis-aligned rectangular buildings that could produce that exact skyline.
Problem
The outline made by buildings at sunset is called a skyline. From the skyline alone, it is usually impossible to know exactly how many buildings exist. However, if every building is an axis-aligned rectangle, it is possible to determine the minimum number of buildings needed to produce the given skyline.
Given the points where the skyline height changes, compute this minimum number of buildings.
Input
The first line contains n, the number of height-change points in the skyline. (1 ≤ n ≤ 50,000)
Each of the next n lines contains x and y, the coordinate of a point where the skyline height changes as you scan from left to right, and the height from that point onward. (1 ≤ x ≤ 1,000,000, 0 ≤ y ≤ 500,000)
The x-coordinate of the first point is always 1.
Output
Print the minimum number of buildings needed.
Hint
The input describes the skyline below.
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....XXXXXXXXXXXX
It can be formed with six buildings as shown below, and no smaller number of buildings is possible.
..........................
.....22.........333.......
.111.22.......XX333XX.....
X111X22XXX....XX333XXXXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......5555555.....
4444444444....5555555XXXXX
..........................
.....XX.........XXX.......
.XXX.XX.......XXXXXXX.....
XXXXXXXXXX....666666666666