[Sweep Line Algo][Divide And Conquer][Heap]The Skyline Problem

1. Example
TRICK: 
Start look max(compare with pq.peek(), peek() not change, skip this start ), 
End look min ( remove this height, pq.peek() look for min)
15   |          __
12   |         |    |____    
10   |       _|_| |__    |      ___
       |      |  |  | |    |   |      |     _| _  
 8    |      |  |  | |    |   |      |    |  |    |
       |___|_|_| |__|_ |___|__|  |_  |_
              2 3 7  9   12   15  20  24
                                        19
[2 9 10]
[3 7 15]
[5 12 12 ]
[15 20 10]
[19 24 8]


15   |          __
12   |         |    |____    
10   |       _|            |        ___
       |      |               |       |       | _  
 8    |      |               |       |           |
       |___|__      __ |_     |___ __|_
              2 3 7  9   12   15  20  24
                                        19
[2 10]
[3 15]
[7 12]
[12 0]
[15 10]
[20 8]
[24 0]

References:
http://yuanhsh.iteye.com/blog/2217735
http://www.shuatiblog.com/blog/2014/07/01/The-Skyline-Problem/
2. Implementation
Q1: find the highest edge and keep scrolling down?
A1: highest edge 3  15
                            7 15
                            7 12
                           12 12
                             2 10
                            9  10
                         15 10
                          20 10
                         24 8
2 0
12 0
15 0
24 0
Q1: Priority Queue <-> Heap

3,7,2,4,1,5
min heap default
   3
-----
   3
7
-----
    3
7   2
-----
  2
7  3  heapify
------
    2
  7 3
4
-----
   2
 4    3
7        heapify
-------
     2
  4   3
7 1
------
     2
  1   3
7  4     heapify
------
     1
  2   3
7 4      heapify
---------
     1
  2     3
7 4  5     DONE!!

1  2  3   4   5  6
1, 2, 3,  7, 4,  5
1,,2,,4,,,3,,7,,,5
[3 7 2 4 1 5]
Left child(i) = at position 2i
Right child(i) = at position 2i+1
Parent(i) = at position floor(i/2)
  0  1  2  3 4  5 6  7  8  9 10
["",A,B,C,D,E,F,G,H, I, J,..]<= Queue
                           A
               B 2(P)          C
      D 4         E         F     G  <= Heap
 H 8(L) I    I9(R)
1. Insert
Insert new element into the heap at the next available slot ( next available slot ( hole )
2. DeleteMin
Move last element into hole at root
Construct heap from initial set of N items
  Solution 1  Perform N inserts  O(N log2 N) worst-case
  Solution 2 (use buildHeap())  Randomly populate initial heap with structure property
  Perform a percolate-down from each internal node (H[size/2] to H[1]) (H[size/2] to H[1])
 To take care of heap order property
Height of heap is
 insert: O (lg N ) for each insert
 log 2 N  (g )  In practice, expect less
 buildHea p () insert: O ( N ) for N inserts
 deleteMin: O(lg N)
  decreaseKey: O(lg decreaseKey: O(lg N)
 increaseKey: O(lg N)
 remove: O(lg remove: O(lg N)


把所有的turning points 放在一起，根据coordination从小到大sort 。
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把 volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume

if ( h[1] < 0 ) { 

 pq.offer(-h[1]); } 

 else {

 pq.remove(h[1]); }

// Time:O(nlogn) , Space:O(n)
public List getSkyLine(int[][] buildings)
{



    List result = new ArrayList<>();
    // validate the input
    if ( buildings == null || buildings.length ==0 || buildings[0].length ==0 )
        return result;
   




    List height = new ArrayList<>();
    for (int[] b:buildings)
    {
        height.add( new int[]{ b[0], -b[2]   });// start , -height
        height.add( new int[]{ b[1],  b[2]   });// end , height
    }    



   
    Collections.sort(   height, new Comparator(){
        public int compare(int[] a, int[] b)
        { 
            if ( a[0] != b[0]) return a[0] - b[0];
            return a[1]-b[1];
        }
        
    }   );






    Queue pq = new PriorityQueue<>(){
        public int compare(Integer a, Integer b)
           return b-a;// descending        
    }); 
   
    


 // Input : [2,-10][3,-15][5,-12][7,15][9,10][12,12][15,-10][19,-8][20,10][24,8]
//  Result: [2 10],[3 15],[7 12],[12 0],[15 10],[20 8],[24, 0]
//[2 -10]=>    (10 0),         pre=0!=10  ,RES.ADD[2,10], pre =10
//[3,-15]=>    (15 10,0),      pre=10!=15 ,RES.ADD[3,15], pre =15
//[5 -12]=>    (15 12 10 0),   pre =15==15,RES NOT ADD  , pre =15
//[7,15]remove 15 (12 10 0),    , pre =15!=12,RES.ADD[7,12], pre =12
//[9,10]remove 10 (12 0 ),        pre =12==12,RES NOT ADD,   pre =12
//[12,12]remove12 (0),            pre =12!=0 ,RES.Add[12,0], pre = 0
//[15,-10]        (10 0)          pre =0!= 10,RES.Add[15,10],pre =10
//[19,-8]         (10 0 8)        pre =10==10,RES NOT ADD   ,pre =10
//[20,10]         (8 0)           pre =10!= 8,RES.ADD[20,8], pre = 8
//[24,8]          (0)             pre =0!=8  ,RES.ADD[24,0]
    pq.offer(0);
    int prev = 0;
    for (int[] h: height)
    {
         if ( h[1] < 0 )
         {
            pq.offer(-h[1]);
         }
         else 
         {
            pq.remove(h[1]);
         }

         int cur = pq.peek();
         if ( prev != cur )
         {
              result.add(   new int[] {h[0], cur});
              prev = cur;
         }
    }


    
     return result;

}

public int[] skyline( List bds, int min, int max)
{


     int[] output = new int[max-min];


     List[] edges = new List[max-min];
     for (int i = 0; i < edges.length;i++)
         edges[i] = new ArrayList();




     for (Building b: bds)
     {
            edges[b.from].add( new Edge(b, true) );
            edges[b.to].add(   new Edge(b, false)  );
     }



     Queue heap = new PriorityQueue(100,
new ComparatoR
     {
       public int ocmpare (Buildign b1, Building b2)
          return b2.hieght-b1.height;
     });


    
     
     for (int i = 0 ; i < edges.length; i++)
     {
         for ( Edge e, edges[i])
         {
              if ( e.isEnter)
                   heap.add(e.building);
              else
                   heap.remove(e.building);
         }


         if (!heap.isEmpty())
              output[i] = heap.peek().height;
     }
}

static class Edge {
    Building building;
    boolean is Enter;
    public Edge(Building old, boolean enter)
    {
        building = old;
        isEnter = enter;
    }
}
static class Building
{
    int from;
    int to;
    int height;
    public Building (int a, int b, int c)
    {
      from=a; to= b;height=c; 
    }
}

3. Similar Ones
[1]Given n line segments, find if any two segments intersect
http://www.geeksforgeeks.org/given-a-set-of-line-segments-find-if-any-two-segments-intersect/





[2]这样的，两个input，第一个是一个机器的total_mem，第二个是一堆job，每个job包含starting_time，duration，mem_needed，mem_needed就是说这个工作需要这么多的memeory。要求是输出bool，表示是否在任意时间内，所有重叠工作的memory总和都不能超过total_mem。也就是测试这个机器的total_mem够不够大。
每个job有一个time interval, sorted according to start time, loop each interval, for each interval, loop previous interval to see if previous jobs ended. Calculate memory and compare with total memory. Time complexity will be O(n^2). 没有前面提供的优化~
一个job变成两个事件点
Event{. visit 1point3acres.com for more.
bool is_in;
int time;
int mem_used;.
}

比如job 从 0开始 10结束，用了200mem
Event{true,0,200}, Event{false,10,200}
按照time排序，time相同，is_in = false的优先。

然后你扫过去， is_in=true的你就加mem,is_in=false的你就-mem.每个事件点，你会加或减一次，每加或减一次后，就check是不是超过总的。