The Skyline Problem

This problem is a little hard. Given a series of buildings, we reserve a queue where in the queue the buildings is sorted by their right sides' position and their height is descending all the way. Note that the won't be a building in the queue contains right top point of another building in the queue.

We we are going to add next building, first from the head of queue we poll all buildings whose right side is on the left of left side of current building as these buildings won't affect skyline after current building's left side. Then we removes all buildings in the queue whose top right point is contained by current building. At last we insert current building to a proper position in the queue.

To build the result, we add upstair points when we first meet a buildings if it is higher than any buildings in the queue. Noted that many buildings may have the same left side position, so when adding upstair points, we first check last points and make sure the buildings with same left side position only contribute one highest upstair point in the result. We add downstair points when poll bulidings whose right side is at the left of current building as well as in the end of program to empty queue.

There are two ways to implement this algorithm. The first is using LinkedList and insertion method when adding items into the queue. The other method is using a PriorityQueue and let the PriorityQueue to sort buildings for us.

The LinkedList solution:

import java.util.*;

public class TheSkylineProblem {
    public List<int[]> getSkyline(int[][] buildings) {
        ArrayList<int[]> result = new ArrayList<int[]>();
        if (buildings.length == 0 || buildings[0].length == 0) return result;

        LinkedList<Integer> queue = new LinkedList<Integer>();
        for (int i = 0; i < buildings.length; i++) {
            int l = buildings[i][0], r = buildings[i][1], h = buildings[i][2];

            while (!queue.isEmpty() && buildings[queue.getFirst()][1] < l) {
                int right = buildings[queue.pollFirst()][1];
                int height = queue.isEmpty() ? 0 : buildings[queue.getFirst()][2];
                int[] newpoint = {right, height};
                result.add(newpoint);
            }

            if (queue.isEmpty() || buildings[queue.getFirst()][2] < h) {

                if (!result.isEmpty() && result.get(result.size() - 1)[0] == l) {
                    int[] last = result.get(result.size() - 1);
                    last[1] = Math.max(last[1], h);
                } else {
                    int[] newpoint = {l, h};
                    result.add(newpoint);
                }
            }


            ListIterator<Integer> iter = queue.listIterator();
            while (iter.hasNext()) {
                int index = iter.next();
                if (buildings[index][1] <= r && buildings[index][2] <= h) {
                    iter.remove();
                }
            }

            if (queue.isEmpty()) queue.addLast(i);
            else {
                iter = queue.listIterator();
                while (iter.hasNext()) {
                    int index = iter.next();
                    if (buildings[index][1] >= r && buildings[index][2] >= h) break;

                    if (buildings[index][2] < h) {
                        iter.set(i);
                        iter.add(index);
                        break;
                    }

                    if (!iter.hasNext()) {
                        iter.add(i);
                        break;
                    }
                }
            }
        }

        while (!queue.isEmpty()) {
            int right = buildings[queue.pollFirst()][1];
            int height = queue.isEmpty() ? 0 : buildings[queue.getFirst()][2];
            int[] newpoint = {right, height};
            result.add(newpoint);
        }

        return result;
    }
}

The PriorityQueue solution:

import java.util.*;

// Solve the skyline problem with priority queue 

public class TheSkylineProblemII {
    public List<int[]> getSkyline(int[][] buildings) {
        ArrayList<int[]> result = new ArrayList<int[]>();
        if (buildings.length == 0 || buildings[0].length == 0) return result;

        final int[][] innerBuildings = buildings;

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(
                buildings.length,
                new Comparator<Integer>() {
                    public int compare(Integer a, Integer b) {
                        return innerBuildings[a][1] - innerBuildings[b][1];
                    }
                });

        for (int i = 0; i < buildings.length; i++) {
            int l = buildings[i][0], r = buildings[i][1], h = buildings[i][2];

            while (!queue.isEmpty() && buildings[queue.peek()][1] < l) {
                int right = buildings[queue.poll()][1];
                int height = queue.isEmpty() ? 0 : buildings[queue.peek()][2];
                int[] newpoint = {right, height};
                result.add(newpoint);
            }

            if (queue.isEmpty() || buildings[queue.peek()][2] < h) {

                if (!result.isEmpty() && result.get(result.size() - 1)[0] == l) {
                    int[] last = result.get(result.size() - 1);
                    last[1] = Math.max(last[1], h);
                } else {
                    int[] newpoint = {l, h};
                    result.add(newpoint);
                }
            }

            Iterator<Integer> iter = queue.iterator();

            boolean flag = true;
            while (iter.hasNext()) {
                int index = iter.next();
                if (buildings[index][1] <= r && buildings[index][2] <= h) {
                    iter.remove();
                    continue;
                } 

                if (buildings[index][1] >= r && buildings[index][2] >= h) {
                    flag = false;
                }
            }

            if (flag) queue.offer(i);
        }

        while (!queue.isEmpty()) {
            int right = buildings[queue.poll()][1];
            int height = queue.isEmpty() ? 0 : buildings[queue.peek()][2];
            int[] newpoint = {right, height};
            result.add(newpoint);
        }

        return result;
    }
}