LeetCode solutions by tgic

The Skyline Problem

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

Last Update 2015-05-28 11:45:44 +0000 View on Github

Source code Read on Github

  1 public class Solution {
  2     static int li(int[] building){
  3         return building[0];
  4     }
  5 
  6     static int ri(int[] building){
  7         return building[1];
  8     }
  9 
 10     static int hi(int[] building){
 11         return building[2];
 12     }
 13 
 14     static class SortedBuilds {
 15         int[][] buildings;
 16         int p = 0;
 17 
 18         PriorityQueue<int[]> inserted = new PriorityQueue<>((a, b) -> li(a) - li(b));
 19 
 20         SortedBuilds(int[][] buildings) {
 21             this.buildings = buildings;
 22         }
 23 
 24         boolean hasNext(){
 25             return p < buildings.length || !inserted.isEmpty();
 26         }
 27 
 28 
 29         int[] next(){
 30 
 31             if(p < buildings.length && !inserted.isEmpty()){
 32 
 33                 if(li(buildings[p]) < li(inserted.peek())){
 34                     return buildings[p++];
 35                 }else{
 36                     return inserted.poll();
 37                 }
 38 
 39             } else if(p < buildings.length ){
 40                 return buildings[p++];
 41             } else { // !inserted.isEmpty())
 42                 return inserted.poll();
 43             }
 44 
 45         }
 46 
 47         void insert(int[] building){
 48             inserted.add(building);
 49         }
 50     }
 51 
 52     public List<int[]> getSkyline(int[][] buildings) {
 53 
 54         List<int[]> all = new ArrayList<>();
 55         if(buildings.length == 0) return all;
 56 
 57         SortedBuilds sortedBuilds = new SortedBuilds(buildings);
 58 
 59         int[] a = sortedBuilds.next();
 60 
 61         while (sortedBuilds.hasNext()){
 62             int[] b = sortedBuilds.next();
 63 
 64             if(ri(a) == li(b) && hi(a) == hi(b)){
 65                 a = new int[]{li(a), ri(b), hi(a)};
 66                 continue;
 67             }
 68 
 69             // a.r b.l
 70             if(ri(a) <= li(b)){
 71                 all.add(new int[]{li(a), hi(a)});
 72 
 73                 if(ri(a) < li(b)){
 74                     all.add(new int[]{ri(a), 0});
 75                 }
 76 
 77                 a = b;
 78                 continue;
 79             }
 80 
 81             // a.l b.l
 82             if(li(a) == li(b)){
 83 
 84                 // make a higher than b
 85                 if(hi(a) < hi(b)){
 86                     sortedBuilds.insert(a);
 87                     a = b;
 88                     continue;
 89                 }
 90 
 91                 if(ri(a) < ri(b)){
 92                     sortedBuilds.insert(new int[]{ri(a), ri(b), hi(b)});
 93                 }
 94                 // else drop b (b inside a)
 95                 continue;
 96             }
 97 
 98             //
 99             if(hi(a) < hi(b)){
100 
101                 all.add(new int[]{li(a), hi(a)});
102 
103                 if(ri(a) > ri(b)){
104                     sortedBuilds.insert(new int[]{ri(b), ri(a), hi(a)});
105                 }
106 
107                 a = b;
108                 continue;
109             }
110 
111             // a.h >= b.h
112 
113             if(ri(a) < ri(b)){
114                 sortedBuilds.insert(new int[]{ri(a), ri(b), hi(b)});
115             }
116             // else drop b (b inside a)
117         }
118 
119         all.add(new int[]{li(a), hi(a)});
120         all.add(new int[]{ri(a), 0});
121 
122         return all;
123     }
124 }
comments powered by Disqus

LeetCode solutions by tgic

  • LeetCode solutions by tgic
  • [email protected]
  • Creative Commons License
    This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
  • tg123
  • tg123/leetcode

LeetCode java solutions by tgic