# Java Scan Line Algorithm with Self-explanation

• ``````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);
}
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()) {
} else {
if (queue.peek() < 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()) {
} else {
if (edge.height > queue.peek()) {