Java Scan Line Algorithm with Self-explanation


  • 0
    class Edge {
        int x;
        int height;
        boolean isStart;
        Edge(int x, int height, boolean isStart) {
            this.x = x;
            this.height = height;
            this.isStart = isStart;
        }
    }
    public class Solution {
        public List<int[]> getSkyline(int[][] buildings) {
            // scan line algorithm
            List<int[]> result = new ArrayList<int[]>();
            if (buildings == null || buildings.length == 0) {
                return result;
            }
            List<Edge> list = new ArrayList<Edge>();
            for (int i = 0; i < buildings.length; i++) {
                int[] curr = buildings[i];
                Edge start = new Edge(curr[0], curr[2], true);
                Edge end = new Edge(curr[1], curr[2], false);
                list.add(start);
                list.add(end);
            }
            Comparator<Edge> comparator = new Comparator<Edge>() {
                public int compare(Edge a, Edge b) {
                    if (a.x == b.x) {
                        // when positions of edges are the same
                        if (a.isStart && b.isStart) {
                            // if two edges are start edge (left), the highest edge comes first
                            return b.height - a.height;
                        }
                        if (!a.isStart && !b.isStart) {
                            // if tow edges are end edge (right), the lowest edge comes first 
                            return a.height - b.height;
                        }
                        // when two edges one is the end edge of some building, and another one is start edge
                        // of some building, start edge comes first
                        if (a.isStart) {
                            return -1;
                        } else {
                            return 1;
                        }
                    } else {
                        // when positions of edge are not the same
                        return a.x - b.x;
                    }
                }
            };
            Collections.sort(list, comparator);
            PriorityQueue<Integer> queue = new PriorityQueue<Integer>(10, Collections.reverseOrder());
            for (Edge edge : list) {
                if (edge.isStart) {
                    // start edge
                    if (queue.isEmpty()) {
                        result.add(new int[]{edge.x, edge.height});
                    } else {
                        if (queue.peek() < edge.height) {
                            result.add(new int[]{edge.x, edge.height});
                        }
                    }
                    // offer a single instance into queue
                    queue.offer(edge.height);
                } else {
                    // end edge
                    // remove a single instance from queue
                    queue.remove(edge.height);
                    if (queue.isEmpty()) {
                        result.add(new int[]{edge.x, 0});
                    } else {
                        if (edge.height > queue.peek()) {
                            result.add(new int[]{edge.x, queue.peek()});
                        }
                    }
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

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