[leetcode/lintcode 题解] Amazon 面试题:数飞机
資深大佬 : zzzrf 3
给出飞机的起飞和降落时间的列表,用序列 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)