Maximum Population Year

Link

Description

You are given a 2D integer array logs where each logs[i] = [birthi, deathi] 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 [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 <= birthi < deathi <= 2050

Solution

Original Solution

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        vector<pair<int, char>> events;
        for (const auto& log : logs) {
            events.emplace_back(log[0], 's');
            events.emplace_back(log[1], 'e');
        }

        sort(events.begin(), events.end(), [](const auto& lhs, const auto& rhs) {
            return lhs.first < rhs.first || (lhs.first == rhs.first && lhs.second < rhs.second);
        });

        int currentOverlap = 0, maxOverlap = 0;
        int res = events[0].first;
        for (const auto& event : events) {
            if (event.second == 's') {
                currentOverlap++;
            } else {
                currentOverlap--;
            }
            if (currentOverlap > maxOverlap) {
                maxOverlap = currentOverlap;
                res = event.first;
            }
        }
        return res;
    }
};

• Time complexity: \(O(n\log n)\).

Line Sweep Solution

class Solution {
public:
    int maximumPopulation(vector<vector<int>>& logs) {
        int diff[2051]{}, res = 0;
        for (const auto& log : logs) {
            diff[log[0]]++;
            diff[log[1]]--;
        }
        for (int i = 1950; i < 2051; i++) {
            diff[i] += diff[i - 1];
            res = diff[i] > diff[res] ? i : res;
        }
        return res;
    }
};

• Time complexity: \(O(n)\).