The Skyline Problem

The Skyline Problem

When I first started working on the problem, my idea is to insert and merge new intervals into the result list while loop through buildings. For the result list, I only need to grab the last two elements and compare with the new interval and do all the merging and insertion stuff. The solution can only pass part of the test cases. The reason is the new segment might have a start time which is earlier than the last two points. It's not enough to only compare it against the last two elements of the result list.

My solution fails in the above cases. When calculating the skyline of 1, 2 and 3, 3's starting point is before p3 and p4. The correct result after inserting 3 is create a new p3 and remove the original p3 and p4. It tells me that for each new interval, I need to go through all the existing points in result list, find the correct position to insert the new interval and than possibly modify many subsequent points in the result list.

I started my search of correct answer and this one looks very interesting. https://leetcode.com/discuss/37630/my-c-code-using-one-priority-queue-812-ms

Copy the explanation from the link above here,

"The idea is to do line sweep and just process the buildings only at the start and end points. The key is to use a priority queue to save all the buildings that are still "alive". The queue is sorted by its height and end time (the larger height first and if equal height, the one with a bigger end time first). For each iteration, we first find the current process time, which is either the next new building start time or the end time of the top entry of the live queue. If the new building start time is larger than the top one end time, then process the one in the queue first (pop them until it is empty or find the first one that ends after the new building); otherwise, if the new building starts before the top one ends, then process the new building (just put them in the queue). After processing, output it to the resulting vector if the height changes."

The explanation is very useful, but you may need to read it a couple of times before it makes sense to you. The fundamental principle is that at any time, the last element in result list is the starting point of the last segment. This point extends until the top point of the priority queue.

Try the code with the example below is the best way to understand the algorithm.

1:  public class Solution {  
2:    public class Pos {  
3:      int h;  
4:      int x;  
5:      public Pos(int hh, int xx) {  
6:        h = hh;  
7:        x = xx;  
8:      }  
9:    }  
10:    public List<int[]> getSkyline(int[][] buildings) {  
11:      LinkedList<int[]> res = new LinkedList<int[]> ();  
12:      if(buildings.length == 0)  
13:        return res;  
14:      PriorityQueue<Pos> queue = new PriorityQueue<Pos> (1, new Comparator<Pos>() {  
15:        @Override  
16:        public int compare(Pos p1, Pos p2) {  
17:          if(p1.h != p2.h)  
18:            return p2.h-p1.h;  
19:          else  
20:            return p1.x-p2.x;  
21:        }  
22:      });  
23:      int curr = 0;  
24:      int currX = 0;  
25:      int currH = 0;  
26:      while(curr<buildings.length || !queue.isEmpty()) {  
27:        //when buildings[curr] overlaps with segments already inserted  
28:        if(queue.isEmpty() || (curr<buildings.length && buildings[curr][0] <= queue.peek().x)) {  
29:          currX = buildings[curr][0];  
30:          //Insert the end point of this segment and the following segments' end point having the same start point into the queue  
31:          while(curr<buildings.length && buildings[curr][0]==currX) {  
32:            queue.add(new Pos(buildings[curr][2], buildings[curr][1]));  
33:            curr++;  
34:          }  
35:        }  
36:        //buildings[curr] has no overlap with already inserted segments  
37:        //Finish all the inserted segments before dealing with buildings[curr]  
38:        else {  
39:          currX = queue.peek().x;  
40:          //For end points which terminate earlier than currX and not has high as currX, they will be invisible in the skyline  
41:          //So we should directly pop them away  
42:          while(!queue.isEmpty() && queue.peek().x <= currX)  
43:            queue.poll();  
44:        }  
45:        //If queue is empty, it's the last point. The height should be zero  
46:        currH = queue.isEmpty() ? 0 : queue.peek().h;  
47:        //If the newly inserted point has the same height as the last element of result list, there is no need to insert it. Because the last element of result list will extend until the top of priority list, which must have a larger end point  
48:        if(res.isEmpty() || res.getLast()[1]!=currH) {  
49:          res.add(new int[]{currX, currH});  
50:        }  
51:      }  
52:      return res;  
53:    }  
54:  }