The Skyline Problem

Leave a comment

March 9, 2017 by oneOokay

只需要考虑critical points: 哪些是critical points?每一个building的left和right.

从小到大遍历每一个critical point: 当前点的高度应该是覆盖该点的building的height的最大值. 用Set/Tree来存这些critical points. 但是不一定把当前点和它的高度加入到res里面.看后面.

如何判断/找到覆盖某一点的building的height?

一个building的覆盖功能在经过这个building left的时候开始,right的时候结束.

所以用一个按照height排序的MaxHeap.

如何loop?从小到大遍历点还是遍历所有的building? 从小到大遍历点.

对于这个点,我们怎么知道它属于哪个building?它属于的building的height是多少?是start点还是end点? 所以用一个TreeMap<Integer, List<int[]>>: key为点的坐标值,value List<>为与这个点有关系的那条”边”, 也就是[start, end, height]. 如果key == start说明它就是起点,否则就是终点.而且也能够知道height.

所以:

  1. loop through buildings: 把start和end以及他们对应的int[] array都放到TreeMap里面.
  2. 遍历TreeMap. (用for(Map.Entry)来遍历, 对于每一个map entry:
    1. 它的每一个int[] array:
      • 如果当前的点对于int[] array来说是一个起点,把这个int[] array加入到max heap里面. building top开始起到覆盖作用了.
      • 如果当前的点对于int[] array来说是一个终点,把array从heap里面移除. 这个building top的覆盖作用从此消失.
    2. 如果heap为空,说明当前是地平线,加入(key, 0)到res
    3. heap不为空:
      1. res为空
      2. 或者当前的点的高度(heap.peek()[2])和之前的skyline的值(res最后一个元素的值)不同的话, 加入(key, heap.peek()[2])到res.
      3. 如果当前的点的高度和之前的skyline的值一样,说明当前的点是被之前的building top覆盖住的,所以不需要加到res里.
  3. 返回res.
public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> res = new ArrayList<>();
        if (buildings == null || buildings.length == 0 || buildings[0].length == 0)
            return res;
//处理critical points
        TreeMap<Integer, List<int[]>> points = new TreeMap<>();
        for (int[] building : buildings){
            if (!points.containsKey(building[0]))
                points.put(building[0], new ArrayList<int[]>());
            if (!points.containsKey(building[1]))
                points.put(building[1], new ArrayList<int[]>());
            points.get(building[0]).add(building);
            points.get(building[1]).add(building);
        }
        //一个maxHeap
        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2] - a[2]);
        int curPoint, curHeight;
        for (Map.Entry<Integer, List<int[]>> entry : points.entrySet()){
            curPoint = entry.getKey();
//处理building top的覆盖问题
            for (int[] arr : entry.getValue()){
                if (curPoint == arr[0])
                    maxHeap.add(arr);
                else
                    maxHeap.remove(arr);
            }
            //处理完毕进行height的判断是否加入res中
            if (maxHeap.isEmpty())
                res.add(new int[]{curPoint, 0});
            else if (res.size() == 0 || res.get(res.size() - 1)[1] != maxHeap.peek()[2])
                res.add(new int[]{curPoint, maxHeap.peek()[2]});
        }
        return res;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: