218.The-Skyline-Problem

218. The Skyline Problem

题目地址

https://leetcode.com/problems/the-skyline-problem/

题目描述

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).

Buildings Skyline Contour
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], ...]

代码

Approach 1: Divide and Conquer

class Solution {
  public List<List<Integer>> getSkyline(int[][] buildings) {
        int n = buildings.length;
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    if (n == 0)    return output;
    if (n == 1)    {
      int xStart = buildings[0][0];
      int xEnd = buildings[0][1];
      int y = buildings[0][2];

      output.add(new ArrayList<Integer>() {{ add(xStart); add(y); }});
      output.add(new ArrayList<Integer>() {{ add(xEnd); add(0); }});

      return output;
    }

    List<List<Integer>> lfetSkyline, rightSkyline;
    leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
    rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));

    return mergeSkylines(leftSkyline, rightSkyline);
  }

  public List<List<Integer>> mergeSkylines(List<List<Integer>> left, List<List<Integer>> right) {
    int nL = left.size(), nR = right.size();
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    int x, maxY;
    int pL = 0, pR = 0;
    int currY = 0, leftY = 0, rightY = 0;
    while ((pL < nL) && (pR < nR)) {
      List<Integer> pointL = left.get(pL);
      List<Integer> pointR = right.get(pR);
      // pick up the smallest x
      if (pointL.get(0) < pointR.get(0)) {
        x = pointL.get(0);
        leftY = pointL.get(1);
        pL++;
      } else {
        x = pointR.get(0);
        righY = pointR.get(1);
        pR++;
      }
      maxY = Math.max(leftY, rightY);
      // update output if there is a skyline change
      if (currY != maxY) {
        updateOutput(output, x, maxY);
        currY = maxY;
      }
    }

    appendSkyline(output, left, pL, nL, currY);
    appendSkyline(output, right, pR, nR, currY);

    return output;
  }

  public void updateOutput(List<List<Integer>> output, int x, int y) {
     // if skyline change is not vertical - add the new point
    if (output.isEmpty() || output.get(output.size() - 1).get(0) != x) {
      output.add(new ArrayList<Integer>() {{ add(x); add(y); }}); 
    } else {
    // if skyline change is vertical - update the last point
      output.get(output.size() - 1).set(1, y);
    }
  }

/**
 *  Append the rest of the skyline elements with indice (p, n)
 *  to the final output.
 */
  public void appendSkyline(List<List<Integer>> output, List<List<Integer>> skyline, int p, int n, int currY) {
    while (p < n) {
      List<Integer> point = skyline.get(p);
      int x = point.get(0);
      int y = point.get(1);
      p++;
      // update output if there is a skyline change
      if (currY != y) {
        updateOutput(output, x, y);
        currY = y;
      }
    }
  }

}

Approach #2 Sweep line

本题是经典的sweep line问题。

对于sweep line问题我们需要考虑的只有两点：

1. 延水平方向 / 时间方向 ：时间队列 event queue，一般来说是一个优先队列；

2. 延垂直方向 ：sweep line status，即当前的扫描线的状态，一般会将交点按照顺序排序；

对于本题来说，sweep line status可以使用一个multi set来进行维护，当然由于在Java中没有multi set，因此需要使用TreeMap来模拟。

event queue的当然是使用优先队列，问题是如何进行排序，这个才是本题的核心难点。

这里给出结论：

大方向是按照x轴排序，如果x轴相等那么按照height排序；

如果x轴相等，优先判断是否是左端点，如果是左端点，那么优先入队；

如果同时是右端点，那么需要反序入队，就是height小的反而需要排在前面。

public List<List<Integer>> getSkyline(int[][] buildings) {
    List<List<Integer>> res = new ArrayList<>();
    // 对于同x轴，优先将左端点入队列
    // 如果同是右端点，则要反序，y小的先入队列
    // 其余按照正常的height顺序排列即可
    PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
        public int compare(int[] o1, int[] o2) {
            if (o1[0] == o2[0] && o1[2] != o2[2]) return o1[2] - o2[2];
            if (o1[0] == o2[0] && o1[2] == 1 && o2[2] == 1) return o1[1] - o2[1];
            return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
        }
    });
    TreeMap<Integer, Integer> map = new TreeMap<>();
    for (int[] b : buildings) {
        int s = b[0];
        int e = b[1];
        int h = b[2];
        pq.add(new int[]{s, h, 0});
        pq.add(new int[]{e, h, 1});
    }
    while (!pq.isEmpty()) {
        int[] event = pq.poll();
        int x = event[0];
        int h = event[1];
        int status = event[2];        
        int curr_max = map.size() == 0 ? 0 : map.lastKey();
        if (status == 0) {
            if (h > curr_max) res.add(Arrays.asList(x, h));
            map.put(h, map.getOrDefault(h, 0) + 1);
        } 
        else {
            map.put(h, map.get(h) - 1);
            if (map.get(h) == 0) map.remove(h);
            curr_max = map.size() == 0 ? 0 : map.lastKey();
            if (h > curr_max) res.add(Arrays.asList(x, curr_max));
        }

    }
    return res;
}