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

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

在线评测地址

样例 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;     } } 

更多题解参考

大佬有話說 (0)