武汉住建局官方网站爱站网使用体验

题目：

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

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

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

示例：

输入：
birth = [1900, 1901, 1950]
death = [1948, 1951, 2000]
输出： 1901

解题思路：

年份生存人数也就相当于是对每个年龄段的两头进行记录，找每个区间的重叠部分，返回重叠的最大值。

这里我们用到差分数组，出生年份的下标+1，死亡年份的下标-1

Code：

class Solution {
public:int maxAliveYear(vector<int>& birth, vector<int>& death) {int n = birth.size();vector<int> diff(2002, 0); // 定义差分数组diff//先将每个年龄段的两头确定出来，出生年份+1，死亡年份-1for (int i = 0; i < n; i++){int x = birth[i], y = death[i];diff[x] += 1; diff[y+1]-=1; // 表示对区间[x, y]的元素全部加一}int max = 0, idx = 0, sum(0);//计算差分数组的前缀和，每一个前缀和对应问题的每一个位置的人数for (int i = 1900; i <= 2000; ++i) {sum += diff[i];//更新生存人数最多的年份，（不加等号，就默认多个年份生存人数相同且均为最大值，输出其中最小的年份）if (max < sum){max = sum; idx = i;}}return idx;}
};