// Source : https://leetcode.com/problems/the-skyline-problem/

// Author : Hao Chen

// Date : 2015-06-11

/**********************************************************************************

*

* A city's skyline is the outer contour of the silhouette formed by all the buildings

* in that city when viewed from a distance. Now suppose you are given the locations and

* height of all the buildings as shown on a cityscape photo (Figure A), write a program

* to output the skyline formed by these buildings collectively (Figure B).

*

* ^ ^

* | |

* | |

* | +-----+ | O-----+

* | | | | | |

* | | | | | |

* | | +--+------+ | | O------+

* | | | | | | |

* | +-+--+----+ | +------+ | O-+ | O------+

* | | | | | | | | | | |

* | | | | | +-+--+ | | | | O--+  

* | | | | | | | | | | | |

* | | | | | | | | | | | |

* | | | | | | | | | | | |

* | | | | | | | | | | | |

* +--+---------+----+---+----+----+---> +--+--------------O---+---------O--->

*

* https://leetcode.com/static/images/problemset/skyline1.jpg

* https://leetcode.com/static/images/problemset/skyline2.jpg

*

* The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi],

* where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively,

* and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 , and Ri - Li > 0.

* You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

*

* For instance, the dimensions of all buildings in Figure A are recorded as:

* [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .

*

* The output is a list of "key points" (red dots in Figure B) in the format of

* [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline.

* A key point is the left endpoint of a horizontal line segment.

*

* Note that the last key point, where the rightmost building ends, is merely used to mark

* the termination of the skyline, and always has zero height. Also, the ground in between

* any two adjacent buildings should be considered part of the skyline contour.

*

* For instance, the skyline in Figure B should be represented as:

* [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

*

* Notes:

*

* - The number of buildings in any input list is guaranteed to be in the range [0, 10000].

* - The input list is already sorted in ascending order by the left x position Li.

* - The output list must be sorted by the x position.

* - There must be no consecutive horizontal lines of equal height in the output skyline.

* For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable;

* the three lines of height 5 should be merged into one in the final output as such:

* [...[2 3], [4 5], [12 7], ...]

*

* Credits: Special thanks to @stellari for adding this problem,

* creating these two awesome images and all test cases.

*

**********************************************************************************/

/*

* Sweep line with max-heap

* ------------------------

* Notice that "key points" are either the left or right edges of the buildings.

*

* Therefore, we first obtain both the edges of all the N buildings, and store the 2N edges in a sorted array.

* Maintain a max-heap of building heights while scanning through the edge array:

* 1) If the current edge is a left edge, then add the height of its associated building to the max-heap;

* 2) If the edge is a right one, remove the associated height from the heap.

*

* Then we take the top value of the heap (yi) as the maximum height at the current edge position (xi).

* Now (xi, yi) is a potential key point.

*

* If yi is the same as the height of the last key point in the result list, it means that this key point

* is not a REAL key point, but rather a horizontal continuation of the last point, so it should be discarded;

*

* otherwise, we add (xi,yi) to the result list because it is a real key point.

*

* Repeat this process until all the edges are checked.

*

* It takes O(NlogN) time to sort the edge array. For each of the 2N edges,

* it takes O(1) time to query the maximum height but O(logN) time to add

* or remove elements. Overall, this solution takes O(NlogN) time.

*/

class Solution {

public:

vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {

vector< pair<int, int> > edges;

//put all of edge into a vector

//set left edge as negtive, right edge as positive

//so, when we sort the edges,

// 1) for same left point, the height would be descending order

// 2) for same right point, the height would be ascending order

int left, right, height;

for(int i=0; i<buildings.size(); i++) {

left = buildings[i][0];

right = buildings[i][1];

height = buildings[i][2];

edges.push_back(make_pair(left, -height));

edges.push_back(make_pair(right, height));

}

sort(edges.begin(), edges.end());

// 1) if we meet a left edge, then we add its height into a `set`.

// the `set` whould sort the height automatically.

// 2) if we meet a right edge, then we remove its height from the `set`

//

// So, we could get the current highest height from the `set`, if the

// current height is different with preivous height, then we need add

// it into the result.

vector< pair<int, int> > result;

multiset<int> m;

m.insert(0);

int pre = 0, cur = 0;

for (int i=0; i<edges.size(); i++){

pair<int,int> &e = edges[i];

if (e.second < 0) {

m.insert(-e.second);

}else{

m.erase(m.find(e.second));

}

cur = *m.rbegin();

if (cur != pre) {

result.push_back(make_pair(e.first, cur));

pre = cur;

}

}

return result;

}

};