Skip to content

The skyline problem

Tim_Gao edited this page Sep 18, 2016 · 1 revision
class Tuple implements Comparable<Tuple> {
    public int h, p;
    public boolean isStart = false;
    public Tuple(int height, int p, boolean isStart){
        this.p = p;
        this.h = height;
        this.isStart = isStart;
    }
    public int compareTo(Tuple other){
        if(this.p != other.p){
            return this.p - other.p;
        } else {
            if (this.isStart && other.isStart){
                return other.h - this.h;
            } else if (!this.isStart && !other.isStart){
                return this.h - other.h;
            } else {
                if(this.isStart){
                    return -1;
                } else {
                    return 1;
                }
            }
        }
    }
}
public class Solution {
    public List<int[]> getSkyline(int[][] buildings) {
        ArrayList<Tuple> skylines = new ArrayList<>();
        for (int[] building: buildings){
            skylines.add(new Tuple(building[2], building[0], true));
            skylines.add(new Tuple(building[2], building[1], false));
        }
        Collections.sort(skylines);
        int prevHeight = 0;
        ArrayList<int[]> res = new ArrayList<>();
        PriorityQueue<Integer> heap = new PriorityQueue(new Comparator<Integer>(){
            public int compare(Integer v1, Integer v2){
                return v2-v1;
            }
        });
        for(Tuple t : skylines){
            if(heap.isEmpty()){
                heap.offer(t.h);
            } else {
                if(t.isStart){
                    heap.offer(t.h);
                } else {
                    heap.remove(t.h);
                }
            }
            if (heap.isEmpty()){
                res.add(new int[]{t.p, 0});
            } else if (prevHeight != heap.peek()){
                res.add(new int[]{t.p, heap.peek()});
                prevHeight = heap.peek();
            }
        }
        return res;
    }
}

Clone this wiki locally