Question

Formatted question description: https://leetcode.ca/all/218.html

218. The Skyline Problem

Level

Hard

Description

A city’s skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).

Image text

The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.

For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ].

The output is a list of “key points” (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.

For instance, the skyline in Figure B should be represented as: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].

Notes:

The number of buildings in any input list is guaranteed to be in the range [0, 10000].
The input list is already sorted in ascending order by the left x position Li.
The output list must be sorted by the x position.
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]

Algorithm

Save the left and right nodes of each line segment to the new vector height, and sort them according to the x coordinate value.

Then traverse to find the inflection point. When finding the inflection point, use a maximum heap to save the current roof height,

When you encounter the left node, insert the height information in the heap,
The height is deleted from the heap when the node on the right is encountered.

Use pre and cur to represent the previous height and the current height respectively,

When cur != pre, it means that there is an inflection point.
Note that when deleting elements from the heap, I use priority_queue to implement it. Priority_queue does not provide delete operations, so another unordered_map is used to mark the elements to be deleted.
When popping from the heap, first see if it has been marked,
- If it has been marked, pop until it is empty or all unmarked values are found. Don’t be careful when sorting externally.
- If the x-coordinates of two nodes are the same, we have to consider other attributes of the nodes to order to avoid redundant answers.
- And the rule of body is
  - If they are all left nodes, sort them from largest to smallest according to the y coordinate,
  - If they are all right nodes, sort from small to large according to the y coordinate, one left node and one right node, let the left node be in the front

Code

Java

import java.util.*;

public class The_Skyline_Problem {

    public static void main(String[] args) {

        The_Skyline_Problem out = new The_Skyline_Problem();

        Solution_Heap s = out.new Solution_Heap();

        // output: [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]
        s.getSkyline( new int[][]{ {2,9,10}, {3,7,15}, {5,12,12}, {15,20,10}, {19,24,8} } )
            .stream().forEach(System.out::println);
    }

    class Solution_Heap {

    public List<List<Integer>> getSkyline(int[][] buildings) {

            List<List<Integer>> result = new ArrayList<>();

            if (buildings == null || buildings.length == 0
                || buildings[0].length == 0) {
                return result;
            }

            List<Edge> edges = new ArrayList<Edge>();

            // add all left/right edges
            for (int[] each: buildings) {
                edges.add(new Edge(each[0], each[2], true));
                edges.add(new Edge(each[1], each[2], false));
            }

            // sort edges, NlogN
            Collections.sort(edges, (a, b) -> {
                if (a.x != b.x) {
                    return Integer.compare(a.x, b.x);
                }

                if (a.isStart && b.isStart) {
                    return Integer.compare(b.height, a.height); // higher edge at front
                }

                if (!a.isStart && !b.isStart) {
                    return Integer.compare(a.height, b.height); // lower edge at front
                }

                return a.isStart ? -1 : 1; // lower edge at front
            });

            // process edges, comparator is reverseOrder()
            PriorityQueue<Integer> heightHeap = new PriorityQueue<Integer>(Collections.reverseOrder());

            for (Edge edge : edges) {

                if (edge.isStart) {

                    if (heightHeap.isEmpty() || edge.height > heightHeap.peek()) {
                        result.add(Arrays.asList( edge.x, edge.height ));
                    }

                    heightHeap.add(edge.height);

                } else {

                    heightHeap.remove(edge.height);

                    if (heightHeap.isEmpty()){
                        result.add( Arrays.asList(edge.x, 0) ); // last point
                    } else if (edge.height > heightHeap.peek()){ // @note: intersect
                        result.add( Arrays.asList(edge.x, heightHeap.peek()) );
                    }
                }
            }
            return result;
        }

        class Edge {
            int x; // x坐标
            int height;
            boolean isStart;

            public Edge(int x, int height, boolean isStart) {
                this.x = x;
                this.height = height;
                this.isStart = isStart;
            }
        }
    }

    // merge sort example
    public class Solution_mergeSort {

        public List<int[]> getSkyline(int[][] buildings) {

            if(buildings == null || buildings.length == 0) {
                return new LinkedList<int[]>();
            }

            return getSkyline(buildings, 0, buildings.length - 1);
        }

        // NlogN
        private LinkedList<int[]> getSkyline(int[][] buildings, int lo, int hi) {

            if (lo < hi) {

                int mid = lo + (hi - lo) / 2;
                return mergeSkylines(getSkyline(buildings, lo, mid), getSkyline(buildings, mid + 1, hi));

            } else {

                //  lo == hi, base case, add the final already-merged building to skyline
                LinkedList<int[]> skyline = new LinkedList<int[]>();

                skyline.add(new int[]{buildings[lo][0], buildings[lo][2]}); // only care about [left-index, height]
                skyline.add(new int[]{buildings[lo][1], 0}); // right-index is just for last right edge

                return skyline;
            }
        }

        // merge two Skylines
        private LinkedList<int[]> mergeSkylines(LinkedList<int[]> skyline1, LinkedList<int[]> skyline2) {

            LinkedList<int[]> skyline = new LinkedList<int[]>();
            int height1 = 0, height2 = 0;

            while(skyline1.size() > 0 && skyline2.size() > 0) {

                int index = 0, height = 0;

                // @note: always remove the smaller index first, so order is guaranteed
                if (skyline1.getFirst()[0] < skyline2.getFirst()[0]) {
                    index = skyline1.getFirst()[0];
                    height1 = skyline1.getFirst()[1];
                    height = Math.max(height1, height2);
                    skyline1.removeFirst();
                } else if (skyline1.getFirst()[0] > skyline2.getFirst()[0]) {
                    index = skyline2.getFirst()[0];
                    height2 = skyline2.getFirst()[1];
                    height = Math.max(height1, height2);
                    skyline2.removeFirst();
                } else {
                    index = skyline1.getFirst()[0];
                    height1 = skyline1.getFirst()[1];
                    height2 = skyline2.getFirst()[1];
                    height = Math.max(height1, height2);
                    skyline1.removeFirst();
                    skyline2.removeFirst();
                }

                if (skyline.size() == 0 || height != skyline.getLast()[1]) {
                    skyline.add(new int[]{index, height});
                }
            }

            // final check
            skyline.addAll(skyline1);
            skyline.addAll(skyline2);

            return skyline;
        }

    }

}

// OJ: https://leetcode.com/problems/the-skyline-problem/
// Time: O(NlogN)
// Space: O(N)
// Ref: https://discuss.leetcode.com/topic/14939/my-c-code-using-one-priority-queue-812-ms
bool cmp(vector<int> &a, vector<int> &b) {
    return a[0] < b[0];
}
class Solution {
public:
    vector<pair<int, int>> getSkyline(vector<vector<int>>& buildings) {
         vector<pair<int, int>> ans;
         sort(buildings.begin(), buildings.end(), cmp);
         int i = 0, x = 0, y = 0, N = buildings.size();
         priority_queue<pair<int, int>> live;// first: height, second: right
         while (i < N || !live.empty()) {
             if (i < N && (live.empty() || live.top().second >= buildings[i][0])) {
                 x = buildings[i][0];
                 while (i < N && buildings[i][0] == x) {
                     live.push(make_pair(buildings[i][2], buildings[i][1]));
                     ++i;
                 }
             } else {
                 x = live.top().second;
                 while (!live.empty() && live.top().second <= x) live.pop();
             }
             y = live.empty() ? 0 : live.top().first;
             if (ans.empty() || ans.back().second != y) ans.push_back(make_pair(x, y));
         }
         return ans;
    }
};

'''
>>> a = []
>>> a.append((3, 5))
>>> a.append((3, -5))
>>> a.append((2, -10))
>>> a.append((2, 10))
>>> a
[(3, 5), (3, -5), (2, -10), (2, 10)]

>>> a.sort()
>>> a
[(2, -10), (2, 10), (3, -5), (3, 5)]



>>> from queue import PriorityQueue
>>> pq = PriorityQueue()
>>>
>>> pq.put([1,2,3])
>>> pq.put([-10,20,30])
>>> pq.put([11,22,33])
>>>
>>> pq
<Queue.PriorityQueue instance at 0x10aec51b8>
>>> pq.queue[0][0]
-10
>>> pq.get()
[-10, 20, 30]
>>> pq.queue[0][0]
1
'''

from queue import PriorityQueue
class Solution:
    def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
        skys, lines, pq = [], [], PriorityQueue()
        for build in buildings:
            lines.extend([build[0], build[1]])
        lines.sort()
        city, n = 0, len(buildings)
        for line in lines: # 对于每一个边界线 lines[i]，找出所有包含 lines[i] 的建筑物
            while city < n and buildings[city][0] <= line:
                pq.put([-buildings[city][2], buildings[city][0], buildings[city][1]]) # 建筑物的高度构建优先队列（大根堆），这里会包括line自己的building
                city += 1
            while not pq.empty() and pq.queue[0][2] <= line: # higher at heap top after negated
                pq.get() # i.e. pop()
            high = 0 # 建筑物的左边界小于等于 lines[i]，右边界大于 lines[i]，则这些建筑物中高度最高的建筑物的高度就是该线轮廓点的高度
            if not pq.empty():
                high = -pq.queue[0][0]
            if len(skys) > 0 and skys[-1][1] == high: # 绿色建筑的左边的line，就要跳过
                continue
            skys.append([line, high])
        return skys

############

import heapq


class Solution(object):
  def getSkyline(self, buildings):
    """
    :type buildings: List[List[int]]
    :rtype: List[List[int]]
    """
    hs = []
    heap = []
    for b in buildings:
      hs.append((b[0], -b[2]))
      hs.append((b[1], b[2]))
    hs.sort()
    ans = []
    pre = cur = None
    for h in hs:
      pos = h[0]
      height = h[1]
      if height < 0:
        heapq.heappush(heap, height)
      else:
        i = heap.index(-height)
        heap[i] = heap[-1]
        heap.pop()
        if i < len(heap):
          heapq._siftup(heap, i)
          heapq._siftdown(heap, 0, i)
      if heap:
        cur = heap[0]
        if cur != pre:
          ans.append((pos, -1 * cur))
          pre = cur
      else:
        ans.append((pos, 0))

    return ans

218 - The Skyline Problem

Question

218. The Skyline Problem

Level

Description

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

218. The Skyline Problem

Level

Description

Algorithm

Code

All Problems

All Solutions