LC 218. The Skyline Problem

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

这题目大约两种做法：

  1. 使用区间数树来不断地更新每个区间的高度。这个做法非常直接，但是代码写出来比较长 参考代码
  2. 另外一种方法类似 LC 1897 Meeting Room III 的方法，将所有building按照X轴排个序，这个序相当于进入视野的顺序，然后不断地更新每个区间的高度。 参考代码

我个人觉得方法2更容易实现，虽然先需要绕点弯子（对X轴进行排序）。此外还有几个小点需要处理：

  1. 这种方法有可能会得到 [x,x,h] 这样的区间表示，所以需要判断 `ev.x > cur`
  2. 在最后面离开视野的时候，需要补上0.
  3. 某些区间是可以进行合并的，比如 [x, y, h2], [y, y2, h2] -> [x, y2, h2]

lintcode 上面也有这道题目，只不过在输出上略微不同而已 参考代码.

另外这题目只能使用Java/C++来写，Python里面是没有现成的TreeSet/TreeMap实现的。

还有就是容器里面的Integer比较相等，必须使用 `x.equals(y)`, 教训啊！ 

import java.util.*;

class Event implements Comparable<Event> {
    int in;
    int x;
    int h;
    int idx;

    public Event(int in, int x, int h, int idx) {
        this.in = in;
        this.x = x;
        this.h = h;
        this.idx = idx;
    }

    public int compareTo(Event it) {
        return x - it.x;
    }
}

class Building implements Comparable<Building> {
    int h;
    int idx;

    public Building(int h, int idx) {
        this.h = h;
        this.idx = idx;
    }

    public int compareTo(Building it) {
        if (this.h != it.h) {
            return this.h - it.h;
        }
        return this.idx - it.idx;
    }
}

class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        int n = buildings.length;
        List<List<Integer>> ans = new ArrayList<>();
        if (n == 0) {
            return ans;
        }

        Event[] events = new Event[2 * n];
        for (int i = 0; i < n; i++) {
            events[2 * i] = new Event(0, buildings[i][0], buildings[i][2], i);
            events[2 * i + 1] = new Event(1, buildings[i][1], buildings[i][2], i);
        }
        Arrays.sort(events);

        TreeSet<Building> ts = new TreeSet<>();
        int cur = events[0].x;

        for (int i = 0; i < events.length; i++) {
            Event ev = events[i];
            int h = 0;
            if (ts.size() > 0) {
                h = ts.last().h;
            }
            if (ev.in == 0) {
                if ((h < ev.h) && (ev.x > cur)) {
                    ArrayList<Integer> t = new ArrayList();
                    t.add(cur);
                    t.add(h);
                    cur = ev.x;
                    ans.add(t);
                }
                ts.add(new Building(ev.h, ev.idx));
            } else {
                if ((h == ev.h) && (ev.x > cur)) {
                    ArrayList<Integer> t = new ArrayList();
                    t.add(cur);
                    t.add(h);
                    cur = ev.x;
                    ans.add(t);
                }
                ts.remove(new Building(ev.h, ev.idx));
            }
        }

        ArrayList<Integer> t = new ArrayList();
        t.add(cur);
        t.add(0);
        ans.add(t);

        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < ans.size(); i++) {
            int j = res.size();
            if ((j > 0) && res.get(j - 1).get(1).equals(ans.get(i).get(1))) {
                continue;
            }
            res.add(ans.get(i));
        }

        return res;
    }
}