(Guaranteed) Really Detailed and Good (Perfect) Explanation of The Skyline Problem


  • 364
    L

    Please, do not ever say detailed explanation if you are not explaining you thoughts very clear!
    Just posting code with some comments is not explanation at all, OK?

    All the posts I have seen with explanations is just different style of obscure.

    Check the following link, that is authentic detailed explanation! your understanding is almost GUARANTEED!

    https://briangordon.github.io/2014/08/the-skyline-problem.html


  • 33
    O

    Oh man! When I opened the link I give you an upvote before I read the article.


  • 1

    me too, impressive


  • 1
    J

    Same here. THAT IS what we call a detailed explanation!


  • 4
    H

    "Our final solution, then, in O(nlogn) time, is as follows. First, sort the critical points. Then scan across the critical points from left to right. When we encounter the left edge of a rectangle, we add that rectangle to the heap with its height as the key. When we encounter the right edge of a rectangle, we remove that rectangle from the heap.

    (This requires keeping external pointers into the heap.)

    Finally, any time we encounter a critical point, after updating the heap we set the height of that critical point to the value peeked from the top of the heap"

    Can someone explain to me about how we would do that in the parentheses? Would we have a min-heap for the right-end point of the rectangles, each one pointing to its respective height in the max-heap?


  • 0
    I

    I am still having hard time translating this explanation into code. Does anyone at least have the pseudocode altogether for the whole problem.


  • 0
    F

    You are right, we need to improve the quality of all the posts!!!


  • 5
    L

    Code based on the same idea. Instead of heap, a BST (TreeMap) is used for log(n) enqueue/dequeue.

    public class Solution {
      public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> ends = new ArrayList<>();
        for (int[] building : buildings) {
          ends.add(new int[] { building[0], 0, building[2] }); // Li, isRightEnd, Hi
          ends.add(new int[] { building[1], 1, building[2] });
        }
        Collections.sort(ends, (a, b) ->
          a[0] == b[0] ?
            (a[1] == b[1] ?
                (a[1] == 0 ? b[2] - a[2] // left end with smaller height comes after left ends with the same coordinate 
                    : a[2] - b[2]) // and vice versa for right ends 
                : a[1] - b[1]) // right end comes after left if coordinates are the same
            : a[0] - b[0]); // regular order when coordinates differ
        TreeMap<Integer, Integer> treemap = new TreeMap<>();
        List<int[]> collect = new ArrayList<>();
        for (int i = 0; i < ends.size(); i++) {
          int[] end = ends.get(i);
          int x = end[0];
          boolean isStart = end[1] == 0;
          int h = end[2];
          int top;
          if (isStart) {
            treemap.put(h, treemap.getOrDefault(h, 0) + 1); // enqueue left end
            top = treemap.lastKey(); // highest building
            if (h == top && treemap.get(top) == 1) { // two buildings can have the same height
              collect.add(new int[] { x, h });
            }
          } else {
            treemap.put(h, treemap.get(h) - 1); // dequeue right end
            if (treemap.get(h) == 0) // no building has this height anymore
              treemap.remove(h);
            if (treemap.isEmpty()) {
              collect.add(new int[] { x, 0 });
            } else {
              top = treemap.lastKey();
              if (h > top) { // dequeuing gives a 2nd highest building
                collect.add(new int[] { x, top });
              }
            }
          }
        }
    
        return collect;
      }
    }
    

  • 0
    Y

    @hide I think heap won't work but only binary search tree.


  • 6
    B

    @liuyifly06 thanks for your detailed post, here is a short implementation of it in Java:

    public class Solution {
        
        public List<int[]> getSkyline(int[][] buildings) {
            Map<Integer, List<int[]>> cps = new TreeMap<>(); // ordered by the critical points
            for(int[] b : buildings) {
                cps.putIfAbsent(b[0], new LinkedList<>());
                cps.putIfAbsent(b[1], new LinkedList<>());
                cps.get(b[0]).add(b);
                cps.get(b[1]).add(b);
            }
    
            // heap for the currently active buildings        
            PriorityQueue<int[]> heap = new PriorityQueue<>(new Comparator<int[]>(){
               public int compare(int[] b1, int[] b2) {
                   return Integer.compare(b2[2], b1[2]);
               } 
            });
    
            List<int[]> res = new ArrayList<>();
            // iterate from left to right over the critical points
            for(Map.Entry<Integer, int[]> entry : cps.entrySet()) {
                int c = entry.getKey();
                List<int[]> bs = entry.getValue();
                
                for(int[] b : bs) {
                    if(c == b[0]) { // this critical point is a left edge of building `b`
                        heap.add(b);
                    } else { // right edge
                        heap.remove(b);
                    }
                }
                
                if(heap.isEmpty()) {
                    // the heap is empty, so the skyline is 0
                    res.add(new int[] { c, 0 });
                } else {
                    int h = heap.peek()[2];
                    if(res.isEmpty() || res.get(res.size() - 1)[1] != h) {
                        // only add the highest rectangle if it different than before
                        res.add(new int[] { c,  h });
                    }
                }
            }
            
            return res;
        }
    }
    

  • 0
    J

    @yjiang01 Actually, HashHeap works. However, we need to write a HashHeap, which is a little complicated


  • 0
    Y

    @balint said in (Guaranteed) Really Detailed and Good (Perfect) Explanation of The Skyline Problem:

    for(Map.Entry<Integer, int[]> entry : cps.entrySet()) {

    it should be

    for(Map.Entry<Integer, List<int[]>> entry : cps.entrySet()) {


  • 0
    E

    @balint for(Map.Entry<Integer, int[]> entry : cps.entrySet()) this statement is wrong, it should be <Integer, List<int[]>>


  • 0
    D

    It's soooo cool... I cannot wait to upvote..


  • 0
    M

    Hi,I am wondering why "delete a specific element from heap" only costs O(N). If you implement it with Priority_queue, it takes O(N) to find the element, and delete+swap takes O(logN)?


  • 8
    Y

    C++ implementation:

    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
            pair<int,int> curr({0,0});
            vector<pair<int,int>> result;
            multiset<pair<int,int>> seq;
            for(auto p:buildings){
                seq.emplace(make_pair(p[0],-p[2]));
                seq.emplace(make_pair(p[1],p[2]));
            }
            multiset<int> height({0});
            for(auto p:seq){
                if(p.second<0)height.emplace(-p.second);
                else height.erase(height.find(p.second));
                if(*height.rbegin()!=curr.second){
                    curr.first=p.first;
                    curr.second=*height.rbegin();
                    result.push_back(curr);
                }
            }
            return result;
        }
    

  • 0

    perfect gif! dashen


  • 1
    M

    @balint

                heap.remove(b);
    

    http://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

    I believe that removing arbitrary object in priority queue in JAVA is O(N) and I think that will undermine your time efficiency. But I still give you upvote.


  • 0
    B

    I think you can directly jump to the last part since all the previous content are irrelevant and unclear.


  • 2
    N

    Whoever written below test case makes no sense for the given problem in the real world.

    [[0,2147483647,2147483647]]

    I mean seriously?? This is test case just to break the program and nothing else.

    Consider a city spanning along entire earth's diameter. I know it is not possible with ocean and all, but for the sake of argument, just consider it.

    Earth Diameter is around 12,700 km

    This is less than 2^14 (16,384)

    If the scale is in meters then, < 2^24
    centimeter then, < 2 ^ 30

    centimeter accuracy for representing the entire earth, that itself is ridiculous.

    Please make some sense while writing the test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.