題目：

給定 N 個(gè)人的出生年份和死亡年份，第 i 個(gè)人的出生年份為 birth[i]，死亡年份為 death[i]，實(shí)現(xiàn)一個(gè)方法以計(jì)算生存人數(shù)最多的年份。

你可以假設(shè)所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之間。如果一個(gè)人在某一年的任意時(shí)期處于生存狀態(tài)，那么他應(yīng)該被納入那一年的統(tǒng)計(jì)中。例如，生于 1908 年、死于 1909 年的人應(yīng)當(dāng)被列入 1908 年和 1909 年的計(jì)數(shù)。

如果有多個(gè)年份生存人數(shù)相同且均為最大值，輸出其中最小的年份。

示例：

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

解題思路：

年份生存人數(shù)也就相當(dāng)于是對(duì)每個(gè)年齡段的兩頭進(jìn)行記錄，找每個(gè)區(qū)間的重疊部分，返回重疊的最大值。

這里我們用到差分?jǐn)?shù)組，出生年份的下標(biāo)+1，死亡年份的下標(biāo)-1

Code：

class Solution {
public:int maxAliveYear(vector<int>& birth, vector<int>& death) {int n = birth.size();vector<int> diff(2002, 0); // 定義差分?jǐn)?shù)組diff//先將每個(gè)年齡段的兩頭確定出來，出生年份+1，死亡年份-1for (int i = 0; i < n; i++){int x = birth[i], y = death[i];diff[x] += 1; diff[y+1]-=1; // 表示對(duì)區(qū)間[x, y]的元素全部加一}int max = 0, idx = 0, sum(0);//計(jì)算差分?jǐn)?shù)組的前綴和，每一個(gè)前綴和對(duì)應(yīng)問題的每一個(gè)位置的人數(shù)for (int i = 1900; i <= 2000; ++i) {sum += diff[i];//更新生存人數(shù)最多的年份，（不加等號(hào)，就默認(rèn)多個(gè)年份生存人數(shù)相同且均為最大值，輸出其中最小的年份）if (max < sum){max = sum; idx = i;}}return idx;}
};