九章算法 | Amazon 面试题：数飞机

给出飞机的起飞和降落时间的列表，用序列 ​interval​ 表示. 请计算出天上同时最多有多少架飞机？

如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

LintCode 领扣

样例 1:

输入: [(1, 10), (2, 3), (5, 8), (4, 7)]
输出: 3
解释: 
第一架飞机在1时刻起飞, 10时刻降落.
第二架飞机在2时刻起飞, 3时刻降落.
第三架飞机在5时刻起飞, 8时刻降落.
第四架飞机在4时刻起飞, 7时刻降落.
在5时刻到6时刻之间, 天空中有三架飞机.

样例 2:

输入: [(1, 2), (2, 3), (3, 4)]
输出: 1
解释: 降落优先于起飞.

算法一 前缀和

在开始时间位置+1架飞机，在结束时间-1架飞机，求一遍前缀和，就是对应时间飞机的数量,

前缀和算法涉及到了对时间离散化，所以这里更推荐扫描线

算法二 扫描线

扫描线，把飞机按开始时间从小到大排序，如果开始时间相同，结束时间小的在前，

扫描一遍，当扫描到开始时间，就会多一架飞机,飞机数+1，当扫描到结束时间就少一架飞机，飞机数-1

答案取扫描过程中的最大飞机数

复杂度分析

时间复杂度

算法一 前缀和

前缀和 O(Time)，Time表示最大时间

算法二 扫描线

扫描线 O(NlogN)，N是飞机数量

空间复杂度

算法一 前缀和

前缀和 O(Time)，Time表示最大时间

算法二 扫描线

扫描线 O(N)，N是飞机数量

public class Solution {
 /**
     * @param airplanes: an array of meeting time airplanes
     * @return: the minimum number of conference rooms required
     */
 static class Node {
 public int time;
 public int cost;
 public Node() {
        }
 // 时间，开始时间cost为1，结束时间cost为-1
 public Node(int time, int cost) {
 this.time = time;
 this.cost = cost;
        }
    }
 //先按照时间升序，再按照cost升序排序
 static Comparator cNode = new Comparator() {
 public int compare(Node o1, Node o2) {
 if(o1.time != o2.time) {
 return o1.time - o2.time;
            }
 return o1.cost - o2.cost;
        }
    };
 public int countOfAirplanes(List airplanes) {
 //扫描线数组
        Listroom = new ArrayList();
 for(int i = 0; i < airplanes.size(); i++) {
            room.add(new Node(airplanes.get(i).start, 1));
            room.add(new Node(airplanes.get(i).end, -1));
        }
 //排序
        Collections.sort(room, cNode);
 int ans = 0;
 int tmp = 0;
 for(int i = 0; i < room.size(); i++) {
            tmp += room.get(i).cost;
            ans = Math.max(ans, tmp);
        }
 return ans;
    }
}

更多题解参考