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

For me it was quite painful problem. I realized quite fast the main idea how you can solve it, but I spend like 2 hours to handling with all corner cases you can have here. So, the idea is the following: let us traverse our buildings from left to right and at each moment of time we decide what is height of current point. Howe we can do it? We need to keep two pieces of information:

  1. So-called active set: what buildings we currently have in given point.
  2. Also, we need to quickly determine the highest building in given point. We will use heap for this purpuse, and if we need to add new building to heap, it is not a problem, it can be done in O(log n). However, we can not easlily delete element from heap (in python you can do it with SortedList, quite powerful data structure), so we perform so-called lazy deletions from heap: it this way our heap can have buildings which already ended, but it does not matter.

Now, let us go the the main algorithm:

  1. For each building, put two tuples of information to points: for left upper corner, we put x, y and also -1, meaning it is starting point and i: index of our building. For right upper corner we put exactly the same, but 1 instead of -1.
  2. Next, we sort our point by x coordinate. If it is equal, we sort them by height multiplied by -1 for left point and by 1 for right point. Why so strange: the reason, that we first want to process starts, from bigger to smaller, and then ends from smaller to bigger.
  3. Also, we put dummy element in our heap and set.
  4. Now, let us iterate through our points and: if we meet beginning of some building, we add it to active set, if we meet end, we remove it from active set
  5. If we meet left corner of building and also it is higher than we alredy met so far, that is h > -heap[0][0], then we add this element to ans. Also we add (-h, ind) to our heap (in python heaps are minimum heaps, so we need to keep negative heigth).
  6. If we meet right corner of building and it is less than highest current building, we do nothing with our heap: (actually, what we need to do is to say, that current building is not active any more and we already did this). Corner of building can not be more than than current highest building, because it is ending point. Finally, if h == -heap[0][0], it means, that we need to pop some element from our heap. How many? Here we have our lazy updates: we look if building is active or not and if it is not, we remove and continue, until we have highest building which is active. Finally, if new point we want to add has different height from what we have as the last element of our ans, we add new point to ans: [x, -heap[0][0]]: note, that we add point with height after we removed all inactive elements from heap.
  7. Just return our ans.

Complexity: it is O(n log n), because for every corner we put and remove it from our heap only once, with time O(log n). Space complexity is potentially O(n).

class Solution:
    def getSkyline(self, buildings):
        points  = [(l,h,-1,i) for i, (l,r,h) in enumerate(buildings)]
        points += [(r,h,1,i) for i, (l,r,h) in enumerate(buildings)]
        points.sort(key = lambda x: (x[0], x[1]*x[2]))
        heap, active, ans = [(0,-1)], set([-1]), []
        
        for x, h, lr, ind in points:
            if lr == -1: active.add(ind)
            else: active.remove(ind)
           
            if lr == -1:
                if h > -heap[0][0]: 
                    ans.append([x, h])
                heappush(heap, (-h, ind))
            else:
                if h == -heap[0][0]:   
                    while heap and heap[0][1] not in active: heappop(heap)
                if -heap[0][0] != ans[-1][1]: 
                    ans.append([x, -heap[0][0]])
                
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 0218