lintcode 391. 数飞机

亦凉 2023-07-06 06:17 10阅读 0赞

给出飞机的起飞和降落时间的列表，用序列 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
    解释: 降落优先于起飞.
    注意事项
    如果多架飞机降落和起飞在同一时刻，我们认为降落有优先权。

思路：记录每一辆飞机的起始时间和降落时间，map中按key值排序，所以，从较小时刻开始，有飞机上升则飞机数+1，降落则-1，记录出现的最大值即可

* classs Interval {
        
     *     int start, end;
     *     Interval(int start, int end) {
        
     *         this->start = start;
     *         this->end = end;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param airplanes: An interval array
         * @return: Count of airplanes are in the sky.
         */
        int countOfAirplanes(vector<Interval> &airplanes) {
        
            // write your code here
            map<int,int> count;
            for (auto air : airplanes) {
        
                count[air.start]++;
                count[air.end]--;
            }
            int res=0;
            int sum=0;
            for (auto i : count) {
        
                /* code */
                sum+=i.second;
                res=max(res,sum);
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关 LintCode - 89 K数之和

目录题目来源题目描述示例提示题目解析算法源码 -------------------- 题目来源 [89 · K数之和 - LintCode]

浅浅的花香味﹌/ 2023年10月12日 13:13/ 0 赞/ 16 阅读

相关 lintcode 391. 数飞机

给出飞机的起飞和降落时间的列表，用序列 interval 表示. 请计算出天上同时最多有多少架飞机？样例样例 1: 输入: [(1, 1

亦凉/ 2023年07月06日 06:17/ 0 赞/ 11 阅读

相关【LintCode 简单】326. 滑动数独

1. 描述给定一个3×n3×n 的矩阵 `number`，并且该矩阵只含有1到9的正整数。考虑有一个大小为 3×33×3 滑动窗口，从左到右遍历该矩阵 `number

旧城等待，/ 2023年01月17日 07:42/ 0 赞/ 118 阅读

相关【LintCode 简单】1881. 飞机座位

1. 描述您的任务是为四口之家尽可能多的分配座位。一个四口之家必须占领一排当中连续的四个座位。过道上的座位（例如2C和2D）不被认为是彼此相邻的。一家人被过道分开是可以的，

ゞ浴缸里的玫瑰/ 2023年01月16日 14:27/ 0 赞/ 12 阅读

相关 lintcode491.回文数

lintcode491.回文数判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。注意事项给的数一定保证是32位正整数

本是古典何须时尚/ 2022年06月10日 23:54/ 0 赞/ 145 阅读

相关【LintCode 简单】777. 完全平方数

1.问题描述：给出一个正整数 `num`,写一个函数，要求当这个当`num`为完全平方数时函数返回`True`，否则返回`False` 注意事项 `不要`用诸如sqr

骑猪看日落/ 2022年06月01日 11:44/ 0 赞/ 182 阅读

相关【LintCode 简单】488. 快乐数

1.问题描述：写一个算法来判断一个数是不是"快乐数"。一个数是不是快乐是这么定义的：对于一个正整数，每一次将该数替换为他每个位置上的数字的平方和，然后重复这个过程直到

今天药忘吃喽~/ 2022年06月01日 07:55/ 0 赞/ 247 阅读

相关【LintCode 简单】517. 丑数

1.问题描述：写一个程序来检测一个整数是不是`丑数`。丑数的定义是，只包含质因子 `2, 3, 5` 的正整数。比如 6, 8 就是丑数，但是 14 不是丑数以为

￡神魔★判官ぃ/ 2022年06月01日 05:50/ 0 赞/ 227 阅读

相关【LintCode 简单】491. 回文数

1.问题描述：判断一个正整数是不是回文数。回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。 2.样例： `11`, `121`, `1`, `

快来打我*/ 2022年06月01日 05:30/ 0 赞/ 158 阅读

相关 L391 弦理论

Two pieces of string can join together to form a single string. It is like the two legs

╰半夏微凉°/ 2021年12月23日 08:37/ 0 赞/ 229 阅读