大厂面试真题详解:数飞机

给出飞机的起飞和降落时间的列表,用序列 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;
        }
    }

原创文章,作者:冰封一夏,如若转载,请注明出处:http://www.nncjzx.com/3698.html

关注本站公众号获取更多实时内容

本站微信公众号:二线码农