扫描线算法

// java
class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        List<int[]> all = new ArrayList<>();
        for (int[] e : buildings) {
            all.add(new int[]{e[0], -e[2]}); //left top corner
            all.add(new int[]{e[1], e[2]}); //right top corner
        }
        // sort by x asc, if x is equal , by y desc
        all.sort((o1, o2) -> o1[0]-o2[0]==0 ?  o1[1]-o2[1] : o1[0]-o2[0]);

        List<List<Integer>> res = new ArrayList<>();
        // queue to store heights
        PriorityQueue<Integer> heights = new PriorityQueue<>(Comparator.reverseOrder());
        // when the last build gone, the max height is 0
        heights.add(0);

        // last point's height
        int maxHeight = 0;
        for (int[] p: all) {
            // p[1] < 0 left corner, add height to stack
            // else right corner, remove height from stack
            if (p[1] < 0) heights.add(-p[1]);
            else heights.remove(p[1]);

            // meet change point, add it to the result list
            if (maxHeight != heights.peek()) {
                maxHeight = heights.peek();
                res.add(Arrays.asList(p[0], maxHeight));
            }
        }

        return res;
    }
}

class Event implements Comparable<Event> {
     // 0 -> left point; 1 -> query; 2 -> right point
     int type;
     // position
     int pos;
     // left point, right point -> interval; query -> index
     int para;

			public Event(int type, int pos, int para) {
         this.type = type;
         this.pos = pos;
         this.para = para;
     }

     @Override
     public int compareTo(Event that) {
       // 按x在位置排序，如果x相同，则左端点=》查询事件=》右端点
         return this.pos==that.pos ? this.type-that.type : this.pos-that.pos;
     }
}

 public int[] minInterval(int[][] intervals, int[] queries) {
        /**
         * 方法一：离线算法, 扫描线算法
         * 提示1
         * 如果我们可以将给定的区间和询问重新排序，那么是否可以使得问题更加容易解决？
         *
         * 提示2
         * 我们可以将区间的左右端点以及询问都看成一个「事件」，如果我们将这些「事件」按照位置进行升序排序，那么：
         * 如果我们遇到一个表示区间左端点的「事件」，那么可以将该区间加入某一「数据结构」中；
         * 如果我们遇到一个表示区间右端点的「事件」，那么可以将该区间从「数据结构」中移除；
         * 如果我们遇到一个表示询问的「事件」，那么需要在「数据结构」中寻找最短的区间。
         * 提示3
         * 你能想出一种合适的「数据结构」吗？
         */

        class Event implements Comparable<Event> {
            // 0 -> left point; 1 -> query; 2 -> right point
            int type;
            // position
            int pos;
            // left point, right point -> interval; query -> index
            int para;

            public Event(int type, int pos, int para) {
                this.type = type;
                this.pos = pos;
                this.para = para;
            }

            @Override
            public int compareTo(Event that) {
                return this.pos==that.pos ? this.type-that.type : this.pos-that.pos;
            }
        }

        List<Event> eventList = new ArrayList<>();
        for (int i=0; i<queries.length; i++) {
            eventList.add(new Event(1, queries[i], i));
        }

        for (int i=0; i<intervals.length; i++) {
            int interv = intervals[i][1] - intervals[i][0] + 1;
            // left point
            eventList.add(new Event(0, intervals[i][0], interv));
            // right point
            eventList.add(new Event(2, intervals[i][1], interv));
        }

        eventList.sort(Event::compareTo);

        int[] ans = new int[queries.length];
        PriorityQueue<Integer> seq = new PriorityQueue<>();
        for (Event e: eventList) {
            switch (e.type) {
                case 0: seq.add(e.para); break; //left point
                case 1: ans[e.para] = seq.isEmpty() ? -1
                                    : seq.peek();
                        break; //query
                case 2: seq.remove(e.para); break; //left point
            }
        }
        return ans;
    }

// 双排序队列，滑动查询，优先队列
public int[] minInterval(int[][] intervals, int[] queries) {
    // 区间按照开始位置排序
    Arrays.sort(intervals, (o1, o2) -> o1[0]-o2[0]);

    // 生成query的二元数组并按p[i][0]排序，p[i][0]是query的值， p[i][1]是query的序号
    // p[i][0] 用来从intervals中查询，p[i][1] 用来把结果写入对应的结果数组
    int[][] p = new int[queries.length][2];
    for (int i=0; i<queries.length; i++) {
        p[i][0] = queries[i];
        p[i][1] = i;
    }
    Arrays.sort(p, (o1, o2) -> o1[0]-o2[0]);

    // 按照区间从小到大的优先队列
    // 用来缓存满足当前query的区间
    PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2)-> o1[1]-o1[0]-(o2[1]-o2[0]));
    // 结果集
    int[] ans = new int[queries.length];
    Arrays.fill(ans, -1);
    int index = 0;
    for (int i=0; i<queries.length; i++) {
        // 添加可能满足条件的区间
        while (index<intervals.length && intervals[index][0] <= p[i][0]) {
            pq.add(intervals[index]);
            index++;
        }
        // 过滤掉不满足条件的区间
        while (!pq.isEmpty() && pq.peek()[1] < p[i][0]) {
            pq.poll();
        }

        // 取出最小的区间，如果存在的话
        if (!pq.isEmpty()) {
            int[] tmp = pq.peek();
            ans[p[i][1]] = tmp[1] - tmp[0] + 1;
        }
    }
    return ans;
}