强化四 扫描线

扫描问题的特点
1 事件往往是以区间的形式存在
2 区间两端代表事件的开始和结束
3 按照区间起点排序，起点相同的按照终点拍排序

扫描线要点
将起点和终点打散排序
[[1,3], [2,4]] => [[1,start],[2,start],[3,end],[4,end]]

391 Number of Airplanes in the Sky

• 降落-1 起飞+1
• 遇到一个-1总数-1 遇到一个+1总数+1
• 因为题目说同时有起飞降落时先考虑降落 所以排序时降落的在前

218 The Skyline Problem

• 花花酱 LeetCode 218. The Skyline Problem讲解的非常好

todo
919 Meeting Rooms II
821 Time Intersection

lt391 Number of Airplanes in the Sky

class Pair{
    int index;
    int delta;
    Pair(int index, int delta){
        this.index = index;
        this.delta = delta;
    }
}

public class Solution {
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) {
        // write your code here
        if(airplanes==null || airplanes.size()==0)
            return 0;
        List<Pair> list = new ArrayList<>();
        for(Interval interval : airplanes){
            list.add(new Pair(interval.start, 1));
            list.add(new Pair(interval.end, -1));
        }
        Comparator<Pair> com = new Comparator<Pair>(){
            public int compare(Pair a, Pair b){
                if(a.index!=b.index){
                    return a.index-b.index;
                }else{
                    return a.delta-b.delta;
                }
            }
        };
        Collections.sort(list, com);
        int count = 0;
        int max = Integer.MIN_VALUE;
        for(Pair pair : list){
            count = count + pair.delta;
            max = Math.max(max, count);
        }
        return max;
    }
}

218 The Skyline Problem

class Solution {
    class Event{
        int height;
        int eventType;
        int index;
        Event(int height, int eventType, int index){
            this.height = height;
            //0 entering; 1 leaving
            this.eventType = eventType;
            this.index = index;
        }
    }

    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> results = new ArrayList<>();
        if(buildings==null || buildings.length==0 || buildings[0]==null || buildings[0].length==0)
            return results;
        List<Event> list = new ArrayList<>();
        for(int i=0; i<buildings.length; i++){
            list.add(new Event(buildings[i][2], 0, buildings[i][0]));
            list.add(new Event(buildings[i][2], 1, buildings[i][1]));
        }
        System.out.println(list.size());
        Comparator<Event> com = new Comparator<Event>(){
            public int compare(Event a, Event b){
                if(a.index!=b.index)
                    //坐标不同先按处理坐标小的
                    return a.index-b.index;
                if(a.eventType!=b.eventType){
                    //事件类型不同时 先考虑进入事件
                    return a.eventType-b.eventType;
                }
                if(a.eventType==0){
                    //都是进入事件时 先处理高的
                    return b.height-a.height;
                }
                //都是离开事件时 先处理高的
                return a.height-b.height;
            }
        };
        Collections.sort(list, com);

        Queue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        maxHeap.offer(0);
        for(Event event : list){
            //答案只会出现在有新的大楼进入 或者有大楼离开
            if(event.eventType==0){
                //是进入事件
                if(maxHeap.peek()<event.height){
                    int[] result = {event.index, event.height};
                    results.add(result);
                }
                maxHeap.offer(event.height);
            }else{
                //是离开事件
                maxHeap.remove(event.height);
                if(maxHeap.peek()<event.height){
                    int[] result = {event.index, maxHeap.peek()};
                    results.add(result);
                }
            }
        }
        return results;
    }
}