Question

1854. Maximum Population Year

中文文档

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 <= 100
• 1950 <= 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$.

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

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;
  }
}

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;
  }
};

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
}

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;
}

/**
 * @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;
};