218. The Skyline Problem

I followed one of the top ranked algorithm. You can think the problem in the way that we are constructing buildings from left to right, if there are multiple buildings that we need to construct at the same point, we only need to build the highest one because this one will block the lower ones. With this idea in mind, we need a heap to track all the buildings under construction and the heap is sorted by the height of buildings. When we encounter a new building, first of all, we need to know if the buildings higher than it needs to be completed.

Case 1: the new building is away from the current highest building, then we need to pop out all the buildings that is ended before or right on the same point the highest building ends because these buildings will be blocked by the highest building. Once we are finished with removing these building in the heap, the top in the heap will be the highest building that ends behind and our point will be drawn at this point, i.e. <end point of last top building, height of the current top building>. Note, if current top building has the same height of last top one, we don’t have to push the point to the result because the new top building is connected with the last top building.

Case 2: if the new building is overlapping with the top building, we need to push the new building to the heap and move to next building. Particularly, we need to push all the new buildings starting at the same point into the heap. And then we’ll see if we can push the new building’s starting point into result. The only case will be that the new building’s height is larger than the current top one. Note we have pushed the new building to the heap and the top will be the new building itself. Then the question is how to get the highest building before the new one? Here is the trick, the result itself caches the height too! The end of the result will be the highest building before the new building. So we can compare the last building in the result with the current building. If the top height is larger than the last one, push the starting point of the new building into result.

When I revisited this problem, I made mistakes in
line 7: I was doing "for (i = 0; i < buildings.size(); i++)". This is wrong because even if i == buildings.size(), it's still possible that live heap isn't empty. Therefore, we still need to process the live buildings in the heap until the heap becomes empty.
line 9, 12: This is the case where I need to process the buildings in the heap. So I need to include the case of "i == n". Also, note that x at this moment is the ending point of the highest building in the heap
line 15-18: I need to include overlapping buildings into the heap so that we only output the left point of the highest point starting from the same point. Otherwise, for case "[[1,2,1],[1,2,2],[1,2,3]]", the output will be "[[1,1],[1,2],[1,3],[2,0]]".
line 26: Minor mistake but easy to make.

1:  class Solution {  
2:  public:  
3:    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {  
4:      vector<pair<int, int>> res;  
5:      priority_queue<pair<int, int>> live;  
6:      int i = 0, n = buildings.size();  
7:      while (i < n || !live.empty()) {  
8:        int x = live.empty() ? buildings[i][0] : live.top().second;  
9:        if (i == n || buildings[i][0] > x) {  
10:          // pop out all the buildings that ends before the highest one.  
11:          // and the x position is where the highest building ends.  
12:          while (!live.empty() && live.top().second <= x) live.pop();  
13:        } else {  
14:          x = buildings[i][0];  
15:          while (i < n && buildings[i][0] == x) {  
16:            live.push(make_pair(buildings[i][2], buildings[i][1]));  
17:            i++;  
18:          }  
19:        }  
20:        // Now the x position is the highest building so far  
21:        int h = live.empty() ? 0 : live.top().first;  
22:        // In case1, the new point will have previously highest building's ending x position  
23:        // and the current highest building's height.  
24:        // In case2, the x position will be the current building's position. However, if  
25:        // the current building is not the highest, it will not be pushed into the result.  
26:        if (res.empty() || res.back().second != h) res.push_back(make_pair(x, h));  
27:      }  
28:      return res;  
29:    }  
30:  };