原文链接: https://leetcode-cn.com/problems/living-people-lcci

英文原文

Given a list of people with their birth and death years, implement a method to compute the year with the most number of people alive. You may assume that all people were born between 1900 and 2000 (inclusive). If a person was alive during any portion of that year, they should be included in that year's count. For example, Person (birth= 1908, death= 1909) is included in the counts for both 1908 and 1909.

If there are more than one years that have the most number of people alive, return the smallest one.

Example:

Input: 
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
Output:  1901

Note:

• 0 < birth.length == death.length <= 10000
• birth[i] <= death[i]

中文题目

给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。

 

示例：

输入：
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
输出： 1901

 

提示：

• 0 < birth.length == death.length <= 10000
• birth[i] <= death[i]

通过代码

高赞题解

解题思路：
1.可以换一种思路去理解这个问题，将问题转换为：某公交车从第1900站做为起点，第2000站做为终点。第i个人表示从第birth[i]站上车，在第death[i] + 1站下车。
那么这里为什么是第death[i] + 1下车呢？
是因为题目描述到生于1908年，死于1909年的人应当被列入1908年和1909年的计数,所以我们需要在第death[i]站还需要记录，在下一站在减去。
2.根据思路，定义res[]记录每站数组的人数变化，因为题目范围是1900到2000，我们可以定义数组大小为110个。遍历数组，res[birth[i] - 1900]表示第birth[i]站上一人，res[death[i] + 1 - 1900]表示第death[i] + 1站下一人。
3.整理res[]数组，找到车上人最多的站。

代码块

class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        vector<int> res(110, 0);
        int n = birth.size();
        //生于1908年、死于1909年的人应当被列入1908年和1909年的计数
        for(int i = 0; i < n; i++){
            res[birth[i] - 1900] += 1;
            res[death[i] + 1 - 1900] -= 1;
        }
        int ans = 0;
        //年数的较小值
        int ret;
        for(int i = 1; i <= 101; i++){
            res[i] += res[i-1];
            ans = max(ans, res[i]);
        }
        for(int i = 0; i <= 101; i++){
            if(ans == res[i]){
                ret = i;
                break;
            }
        }
        return ret + 1900;
    }
};

## 统计信息
| 通过次数 | 提交次数 | AC比率 |
| :------: | :------: | :------: |
|    11000    |    16188    |   68.0%   |

## 提交历史
| 提交时间 | 提交结果 | 执行时间 |  内存消耗  | 语言 |
| :------: | :------: | :------: | :--------: | :--------: |