找出人口最多的年份（最有效的解决方案）

Question

给定两个数组；$births包含表示某人出生时间的出生年份列表和表示某人$deaths死亡时间的死亡年份列表，我们如何找到人口最多的年份？

例如，给定以下数组：

$births = [1984, 1981, 1984, 1991, 1996];
$deaths = [1991, 1984];

人口最多的年份应该是1996，因为3在那一年里还有人活着，这是所有年份中人口数量最多的年份。

这是运行的数学：

| 出生 | 死亡 | 人口 |
|-------|-------|------------|
| 1981 | | 1 |
| 1984 | | 2 |
| 1984 | 1984 | 2 |
| 1991 | 1991 | 2 |
| 1996 | | 3 |

假设

我们可以有把握地假设，某人出生的那一年人口可以增加一，而某人死亡的那一年人口可以减少一。所以在这个例子中，1984 年有 2 人出生，1984 年有 1 人死亡，这意味着当年人口增加了 1。

我们也可以安全地假设死亡人数永远不会超过出生人数，并且当人口为 0 时不会发生死亡。

我们还可以安全地假设两者中的年份$deaths和$births永远不会是负值或浮点值（它们总是大于 0 的正整数）。

然而，我们不能假设数组会被排序或者不会有重复的值。

要求

给定这两个数组作为输入，我们必须编写一个函数来返回人口最多的年份。如果输入数组为空或者总体始终为 0，则该函数可能返回0、false、""、 或NULL（可接受任何假值）。如果最高人口出现在多个年份，该函数可能会返回达到最高人口的第一年或任何后续年份。

例如：

$births = [1997, 1997, 1997, 1998, 1999];
$deaths = [1998, 1999];

/* The highest population was 3 on 1997, 1998 and 1999, either answer is correct */

---

此外，包括解决方案的大 O会有所帮助。

---

我最好的尝试如下：

function highestPopulationYear(Array $births, Array $deaths): Int {

    sort($births);
    sort($deaths);

    $nextBirthYear = reset($births);
    $nextDeathYear = reset($deaths);

    $years = [];
    if ($nextBirthYear) {
        $years[] = $nextBirthYear;
    }
    if ($nextDeathYear) {
        $years[] = $nextDeathYear;
    }

    if ($years) {
        $currentYear = max(0, ...$years);
    } else {
        $currentYear = 0;
    }

    $maxYear = $maxPopulation = $currentPopulation = 0;

    while(current($births) !== false || current($deaths) !== false || $years) {

        while($currentYear === $nextBirthYear) {
            $currentPopulation++;
            $nextBirthYear = next($births);
        }

        while($currentYear === $nextDeathYear) {
            $currentPopulation--;
            $nextDeathYear = next($deaths);
        }

        if ($currentPopulation >= $maxPopulation) {
            $maxPopulation = $currentPopulation;
            $maxYear = $currentYear;
        }

        $years = [];

        if ($nextBirthYear) {
            $years[] = $nextBirthYear;
        }
        if ($nextDeathYear) {
            $years[] = $nextDeathYear;
        }
        if ($years) {
            $currentYear = min($years);
        } else {
            $currentYear = 0;
        }
    }

    return $maxYear;
}

上面的算法应该在多项式时间内工作，因为它在最坏的情况O(((n log n) * 2) + k)下n是从每个数组中排序的元素k数，是出生年份数（因为我们知道这k总是k >= y），其中y是死亡年份数。但是，我不确定是否有更有效的解决方案。

我的兴趣纯粹是在现有算法的基础上改进计算复杂度的 Big O。内存复杂性无关紧要。运行时优化也不是。至少它不是主要问题。欢迎任何次要/主要运行时优化，但不是这里的关键因素。

Answer 1

我认为我们可以通过首先排序O(n log n)来获得O(1)额外的空间，然后在迭代时保持当前的数量和全局最大值。我尝试使用当前年份作为参考点，但逻辑似乎仍然有点棘手，所以我不确定它是否已完全解决。希望它可以提供该方法的想法。

JavaScript 代码（欢迎反例/错误）

function f(births, deaths){
  births.sort((a, b) => a - b);
  deaths.sort((a, b) => a - b);

  console.log(JSON.stringify(births));
  console.log(JSON.stringify(deaths));
  
  let i = 0;
  let j = 0;
  let year = births[i];
  let curr = 0;
  let max = curr;

  while (deaths[j] < births[0])
    j++;

  while (i < births.length || j < deaths.length){
    while (year == births[i]){
      curr = curr + 1;
      i = i + 1;
    }
    
    if (j == deaths.length || year < deaths[j]){
      max = Math.max(max, curr);
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    
    } else if (j < deaths.length && deaths[j] == year){
      while (deaths[j] == year){
        curr = curr - 1;
        j = j + 1;
      }
      max = Math.max(max, curr);
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    }

    if (j < deaths.length && deaths[j] > year && (i == births.length || deaths[j] < births[i])){
      year = deaths[j];
      while (deaths[j] == year){
        curr = curr - 1;
        j = j + 1;
      }
      console.log(`year: ${ year }, max: ${ max }, curr: ${ curr }`);
    }

    year = births[i];
  }
  
  return max;
}

var input = [
  [[1997, 1997, 1997, 1998, 1999],
  [1998, 1999]],
  [[1, 2, 2, 3, 4],
  [1, 2, 2, 5]],
  [[1984, 1981, 1984, 1991, 1996],
  [1991, 1984, 1997]],
  [[1984, 1981, 1984, 1991, 1996],
  [1991, 1982, 1984, 1997]]
]

for (let [births, deaths] of input)
  console.log(f(births, deaths));

如果年份范围 的数量级m为n，我们可以存储该范围内每年的计数并具有O(n)时间复杂度。如果我们想变得更奇特，我们还可以O(n * log log m)通过使用允许及时查找后继者的Y-fast trieO(log log m)来获得时间复杂度。