Description#
You are given a 2D integer array logs where each logs[i] = [birthi, deathi] indicates the birth and death years of the ith person.
The population of some year x is the number of people alive during that year. The ith person is counted in year x's population if x is in the inclusive range [birthi, deathi - 1]. Note that the person is not counted in the year that they die.
Return the earliest year with the maximum population.
Example 1:
Input: logs = [[1993,1999],[2000,2010]]
Output: 1993
Explanation: The maximum population is 1, and 1993 is the earliest year with this population.
Example 2:
Input: logs = [[1950,1961],[1960,1971],[1970,1981]]
Output: 1960
Explanation:
The maximum population is 2, and it had happened in years 1960 and 1970.
The earlier year between them is 1960.
Constraints:
1 <= logs.length <= 1001950 <= birthi < deathi <= 2050
Solutions#
Solution 1: Difference Array#
We notice that the range of years is $[1950,..2050]$. Therefore, we can map these years to an array $d$ of length $101$, where the index of the array represents the value of the year minus $1950$.
Next, we traverse $logs$. For each person, we increment $d[birth_i - 1950]$ by $1$ and decrement $d[death_i - 1950]$ by $1$. Finally, we traverse the array $d$, find the maximum value of the prefix sum, which is the year with the most population, and add $1950$ to get the answer.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Where $n$ is the length of the array $logs$, and $C$ is the range size of the years, i.e., $2050 - 1950 + 1 = 101$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
d = [0] * 101
offset = 1950
for a, b in logs:
a, b = a - offset, b - offset
d[a] += 1
d[b] -= 1
s = mx = j = 0
for i, x in enumerate(d):
s += x
if mx < s:
mx, j = s, i
return j + offset
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public int maximumPopulation(int[][] logs) {
int[] d = new int[101];
final int offset = 1950;
for (var log : logs) {
int a = log[0] - offset;
int b = log[1] - offset;
++d[a];
--d[b];
}
int s = 0, mx = 0;
int j = 0;
for (int i = 0; i < d.length; ++i) {
s += d[i];
if (mx < s) {
mx = s;
j = i;
}
}
return j + offset;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int maximumPopulation(vector<vector<int>>& logs) {
int d[101]{};
const int offset = 1950;
for (auto& log : logs) {
int a = log[0] - offset;
int b = log[1] - offset;
++d[a];
--d[b];
}
int s = 0, mx = 0;
int j = 0;
for (int i = 0; i < 101; ++i) {
s += d[i];
if (mx < s) {
mx = s;
j = i;
}
}
return j + offset;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func maximumPopulation(logs [][]int) int {
d := [101]int{}
offset := 1950
for _, log := range logs {
a, b := log[0]-offset, log[1]-offset
d[a]++
d[b]--
}
var s, mx, j int
for i, x := range d {
s += x
if mx < s {
mx = s
j = i
}
}
return j + offset
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function maximumPopulation(logs: number[][]): number {
const d: number[] = new Array(101).fill(0);
const offset = 1950;
for (const [birth, death] of logs) {
d[birth - offset]++;
d[death - offset]--;
}
let j = 0;
for (let i = 0, s = 0, mx = 0; i < d.length; ++i) {
s += d[i];
if (mx < s) {
mx = s;
j = i;
}
}
return j + offset;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| /**
* @param {number[][]} logs
* @return {number}
*/
var maximumPopulation = function (logs) {
const d = new Array(101).fill(0);
const offset = 1950;
for (let [a, b] of logs) {
a -= offset;
b -= offset;
d[a]++;
d[b]--;
}
let j = 0;
for (let i = 0, s = 0, mx = 0; i < 101; ++i) {
s += d[i];
if (mx < s) {
mx = s;
j = i;
}
}
return j + offset;
};
|
