给定两个数组； $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 |
假设
我们可以安全地假设，某个人出生的年份人口可以增加1，某个人死亡的年份人口可以减少1。所以在这个例子中，1984年有2个人出生，1个人死亡，意味着那一年人口增加了1。
我们还可以安全地假设死亡人数不会超过出生人数，当人口为0时不会发生死亡。
我们还可以安全地假设，在$deaths 和 $births数组中的年份数永远不会为负数或浮点数（它们始终是大于0的正整数）。
但是，我们不能假设数组将被排序或不会有重复的值。
要求
我们必须编写一个函数，以这两个数组作为输入，返回人口最高时发生的年份。如果输入的数组为空或人口始终为0，则该函数可以返回0、false、""或NULL（任何falsey值都可以接受）。如果最高人口出现在多个年份，则该函数可以返回第一个达到最高人口的年份或任何后续年份。
例如：
$births = [1997, 1997, 1997, 1998, 1999];
$deaths = [1998, 1999];
/* The highest population was 3 on 1997, 1998 and 1999, either answer is correct */
此外，包括解决方案的 Big O（大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），则上述算法应该在多项式时间内工作。但是，我不确定是否存在更有效的解决方案。
我的兴趣纯粹在于改进现有算法的计算复杂性的大O表示法。内存复杂性不是问题。运行时优化也不是主要关注点。至少这不是关键因素。任何次要/主要运行时优化都可以接受，但这不是关键因素。