Algorithm to Compute the Maximum Population Year

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 <= 100
1950 <= birth < death <= 2050

Hints:
For each year find the number of people whose birth_i ≤ year and death_i > year.
Find the maximum value between all years.

Max Population Year Algorithm by Line Sweep

We can use Line Sweep via the sorted map in C++ and iterate through the years in the ascending order. And add the deta population through the process. The year and max population is updated when we have a larger value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        map<int, int> data;
        for (auto &n: logs) {
            data[n[0]] ++;
            data[n[1]] --;
        }
        int year;
        int maxPop = INT_MIN;
        int pop = 0;
        for (auto &[a, b]: data) {
            pop += b;
            if (maxPop < pop) {
                year = a;
                maxPop = pop;
            }
        }
        return year;
    }
};

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        map<int, int> data;
        for (auto &n: logs) {
            data[n[0]] ++;
            data[n[1]] --;
        }
        int year;
        int maxPop = INT_MIN;
        int pop = 0;
        for (auto &[a, b]: data) {
            pop += b;
            if (maxPop < pop) {
                year = a;
                maxPop = pop;
            }
        }
        return year;
    }
};

The time complexity is O(NLogN) as maintaining/inserting/updating the entries in a sorted map is O(LogN) and there are N logs. and the space complexity is O(N) because we are using a sorted map.

–EOF (The Ultimate Computing & Technology Blog) —