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

1854. Maximum Population Year

Level

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[0] and -(log[1] - 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) {
            birthDeathList.add(log[0]);
            birthDeathList.add(-(log[1] - 1));
        }
        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;
    }
}

All Problems

All Solutions