An interesting problem! But not very easy at first glance. You need to think very clear about how will a keypoint be generated. Since I only learn from others' solutions and am still unable to give my personal explanations, I would suggest you to these solutions: , . Of course, there is still a divide-and-conquer solution on , which is much more difficult to understand :-)

Well, I just rewrite the code in the first solution as follows, by giving those variables more meaning names to help understand it.

1 class Solution { 2 public: 3     vector
     
      
       > getSkyline(vector
       
        
         >& buildings) { 4         int idx = 0, start, height, n = buildings.size(); 5         vector
         
          
            > skyline; 6 priority_queue
           
            
              > liveBuildings; 7 while (idx < n || !liveBuildings.empty()) { 8 if (liveBuildings.empty() || idx < n && buildings[idx][0] <= liveBuildings.top().second) { 9 start = buildings[idx][0];10 while (idx < n && buildings[idx][0] == start) {11 liveBuildings.push(make_pair(buildings[idx][2], buildings[idx][1]));12 idx++;13 }14 }15 else {16 start = liveBuildings.top().second;17 while (!liveBuildings.empty() && liveBuildings.top().second <= start)18 liveBuildings.pop();19 }20 height = liveBuildings.empty() ? 0 : liveBuildings.top().first;21 if (skyline.empty() || skyline.back().second != height)22 skyline.push_back(make_pair(start, height));23 }24 return skyline;25 }26 };
            
           
          
         
        
       
      
     

The Python translation is as follows. Note that since the default heapq is a min heap, we take the negative of the left and right positions and the height of buildings.

1 class Solution: 2     # @param {integer[][]} buildings 3     # @return {integer[][]} 4     def getSkyline(self, buildings): 5         idx, n = 0, len(buildings) 6         liveBuildings, skyline = [], [] 7         while idx < n or len(liveBuildings) > 0: 8             if len(liveBuildings) == 0 or (idx < n and buildings[idx][0] <= -liveBuildings[0][1]): 9                 start = buildings[idx][0]10                 while idx < n and buildings[idx][0] == start:11                     heapq.heappush(liveBuildings, [-buildings[idx][2], -buildings[idx][1]])12                     idx += 113             else:14                 start = -liveBuildings[0][1]15                 while len(liveBuildings) > 0 and -liveBuildings[0][1] <= start:16                     heapq.heappop(liveBuildings)17             height = len(liveBuildings) and -liveBuildings[0][0]18             if len(skyline) == 0 or skyline[-1][1] != height:19                 skyline.append([start, height])20         return skyline