##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1854.html

# 1854. Maximum Population Year

Easy

## Description

You are given a 2D integer array logs where each logs[i] = [birth_i, death_i] indicates the birth and death years of the i-th person.

The population of some year x is the number of people alive during that year. The i-th person is counted in year x’s population if x is in the inclusive range [birth_i, death_i - 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 <= 100
• 1950 <= birth_i < death_i <= 2050

## Solution

Use a list to store each person’s first and last year. That is, for each log in logs, add log and -(log - 1) to the list. Then store the list according to absolute values in ascending order and according to actual values in descending order. Then loop over the list to count the maximum population and store the corresponding year.

• class Solution {
public int maximumPopulation(int[][] logs) {
List<Integer> birthDeathList = new ArrayList<Integer>();
for (int[] log : logs) {
}
Collections.sort(birthDeathList, new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
if (Math.abs(num1) != Math.abs(num2))
return Math.abs(num1) - Math.abs(num2);
else
return num2 - num1;
}
});
int maxYear = 0;
int maxAlive = 0;
int curAlive = 0;
int size = birthDeathList.size();
for (int i = 0; i < size; i++) {
int year = birthDeathList.get(i);
if (year > 0) {
curAlive++;
if (curAlive > maxAlive) {
maxYear = year;
maxAlive = curAlive;
}
} else
curAlive--;
}
return maxYear;
}
}

• // OJ: https://leetcode.com/problems/maximum-population-year/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
int maximumPopulation(vector<vector<int>>& A) {
sort(begin(A), end(A));
int ans = 0, mx = 0, N = A.size();
for (int i = 0; i < N; ++i) {
int yr = A[i], cnt = 0;
for (int j = 0; j < N; ++j) {
cnt += A[j] <= yr && A[j] > yr;
}
if (cnt > mx) {
mx = cnt;
ans = yr;
}
}
return ans;
}
};

• class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
delta =  * 2055
for birth, death in logs:
delta[birth] += 1
delta[death] -= 1

mx = res = cur = 0
for i, v in enumerate(delta):
cur += v
if mx < cur:
mx = cur
res = i
return res

############

# 1854. Maximum Population Year
# https://leetcode.com/problems/maximum-population-year/

class Solution:
def maximumPopulation(self, logs: List[List[int]]) -> int:
people =  * 2051

for b,d in logs:
people[b] += 1
people[d] -= 1
​
for i in range(1, 2051):
people[i] += people[i - 1]

res = 0
mmax = float('-inf')
for i,x in enumerate(people):
if x > mmax:
res = i
mmax = x

return res