Max Population Problem - Given a list of birth years and death years, find the year with the highest population

MaxPop.php

<?php

/**
 * Given an array of birth years and death years, provide the year in which the population count was highest
 *
 * The death year may be null to indicate that the person is still alive to present day
 * We can assume that all death years are always greater than or equal to the birth year
 * We can assume that the person is alive for the entire year on which they are born and the entire year on which they die
 * 
 * Array $dates[ [int, int], ...]
 * Vector of [people => [birth year, death year], ... ]
 * Return Int peakPopulationYear
 * 
 * Runtime O(n + p + n log n * 3)
 */

function getPopulationPeakYear(Array $dates): Int
{
    /* First we must create two sorted arrays, in ascending order, of birth years and death years (this is O(n log n * 3) */
    $birthYears = array_column($dates, 0);
    $deathYears = array_filter(array_column($dates, 1)); // filter out null death years (the person is still alive)
    sort($birthYears);
    sort($deathYears);
        
    $deltas = [];
    $lastDeathYear = array_shift($deathYears);
    $peakYear = $peakPopulation = $population = 0;
    
    /* We can now traverse the list in O(n) time to compute a flat hashtable of deltas */
    foreach ($birthYears as $birthYear) {        
        /* If the death year is less than the current birth year, it's already in the past, then a death has occurred */
        while ($lastDeathYear < $birthYear) {
            if (!isset($deltas[$lastDeathYear])) {
                $deltas[$lastDeathYear] = -1;
            } else {
                $deltas[$lastDeathYear]--;
            }
            
            /* Get the next death year */
            $lastDeathYear = array_shift($deathYears);
        }
        
        /* Increment the delta on the given birth year, because a birth has occurred */
        if (!isset($deltas[$birthYear])) {
            $deltas[$birthYear] = 1;
        } else {
            $deltas[$birthYear]++;
        }
    }
    
    /* A running count of the population can be calculated from each delta (this is O(p)) */
    foreach ($deltas as $year => $delta) {
        $population += $delta; // track the running population count
        
        if ($population > $peakPopulation) {
            $peakYear = $year; // track the peak year changes
            $peakPopulation = $population; // update the peak population count
        }
        
        $deltas[$year] = $population; // you can keep this for debuggin purposes
    }
    
    return $peakYear; // return the peak year
}

$people = [
    [1801, 1887],
    [1943, 1943],
    [1949, 2001],
    [1751, 1803],
    [1881, 1887],
    [1956, 1983],
    [1954, 1983],
    [1801, 1883],
    [1956, null],
    [1944, 1983],
    [1897, 2015],
    [1965, 1997],
    [1941, 1982],
    [1984, null],
];

var_dump(getPopulationPeakYear($people)); // int(1965)