题目描述
给你一个二维整数数组 logs
,其中每个 logs[i] = [birth_i, death_i]
表示第 i
个人的出生和死亡年份。
年份 x
的 人口 定义为这一年期间活着的人的数目。第 i
个人被计入年份 x
的人口需要满足:x
在闭区间 [birth_i, death_i - 1]
内。注意,人不应当计入他们死亡当年的人口中。
返回 人口最多 且 最早 的年份。
样例
输入:logs = [[1993,1999],[2000,2010]]
输出:1993
解释:人口最多为 1,而 1993 是人口为 1 的最早年份。
输入:logs = [[1950,1961],[1960,1971],[1970,1981]]
输出:1960
解释:
人口最多为 2,分别出现在 1960 和 1970。
其中最早年份是 1960。
限制
1 <= logs.length <= 100
1950 <= birth_i < death_i <= 2050
算法
(差分数组) $O(n + m)$
- 初始化一个年份差分数组。
- 对于每个记录,在
birth_i
的位置上加 1,在death_i
的位置上减 1。 - 之后对于每个年份的出生人数,就是从 1950 年开始的前缀和。
时间复杂度
- 假设共有 $m$ 个年份,总时间复杂度为 $O(n + m)$。
空间复杂度
- 需要 $O(m)$ 的额外空间存储年份差分数组。
C++ 代码
class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
const int m = 100, offset = 1950;
vector<int> s(m + 1, 0);
for (const auto &l : logs) {
s[l[0] - offset]++;
s[l[1] - offset]--;
}
int sum = 0;
int tot = 0, ans = -1;
for (int i = 0; i < m; i++) {
sum += s[i];
if (sum > tot) {
tot = sum;
ans = i;
}
}
return ans + offset;
}
};