Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

If landing and flying happens at the same time, we consider landing should happen at first.

Example

For interval list

[
  [1,10],
  [2,3],
  [5,8],
  [4,7]
]

Return3

Solution: 扫描线,按时间从小到大排序,若是起点,count++,若是终点,count--。

注意:同一时间的先算landing,所以也要按flag排序

    public int countOfAirplanes(List<Interval> airplanes) { 
        class Pair{
            int time, flag;

            public Pair(int t, int f){
                this.time = t;
                this.flag = f;
            }
        }
        int count = 0, ans = 0;

        PriorityQueue<Pair> minHeap = new PriorityQueue<Pair>(1, new Comparator<Pair>(){
            public int compare(Pair p1, Pair p2){
                if(p1.time != p2.time){
                    return p1.time - p2.time;
                } else{
                    return p1.flag - p2.flag;
                }

            }
        });
        //flag == 1, 起飞;flag == 0,降落
        for(int i = 0; i < airplanes.size(); i++){
            Pair p1 = new Pair(airplanes.get(i).start, 1);
            Pair p2 = new Pair(airplanes.get(i).end, 0);
            minHeap.add(p1);
            minHeap.add(p2);
        }
        while(!minHeap.isEmpty()){
            Pair p = minHeap.poll();
            if(p.flag == 1){
                count++;

            } else{
                count--;
            }
            ans = Math.max(ans, count);
        }
        return ans;
    }

results matching ""

    No results matching ""