Dado dos matrices; $birthsque contiene una lista de años de nacimiento que indica cuándo nació alguien y que $deathscontiene una lista de años de muerte que indica cuándo alguien murió, ¿cómo podemos encontrar el año en que la población era más alta?

Por ejemplo, dados los siguientes arreglos:

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

El año en que la población era más alta debería ser 1996, porque las 3personas estaban vivas durante ese año, que fue el conteo de población más alto de todos esos años.

Aquí está el cálculo matemático sobre eso:

El | Nacimiento | Muerte | Población |
| ------- | ------- | ------------ |
El | 1981 | El | 1 |
El | 1984 | El | 2 |
El | 1984 | 1984 | 2 |
El | 1991 | 1991 | 2 |
El | 1996 | El | 3 |

Supuestos

Podemos suponer con seguridad que el año en que nace alguien la población puede aumentar en uno y el año en que alguien murió, la población puede disminuir en uno. Entonces, en este ejemplo, 2 personas nacieron en 1984 y 1 persona murió en 1984, lo que significa que la población aumentó en 1 ese año.

También podemos suponer con seguridad que el número de muertes nunca excederá el número de nacimientos y que no puede ocurrir una muerte cuando la población está en 0.

También podemos suponer con seguridad que los años en ambos $deathsy $birthsnunca serán valores negativos o de coma flotante ( siempre son enteros positivos mayores que 0 ).

Nosotros no podemos asumir que las matrices se ordenarán o que no serán valores duplicados, sin embargo.

Requisitos

Debemos escribir una función para devolver el año en que se produjo la mayor población, dados estos dos arreglos como entrada. La función puede devolver 0, false, "", o NULL( cualquier valor Falsey es aceptable ) si las matrices de entrada están vacíos o si la población era siempre a 0 en todas partes. Si la población más alta se produjo en varios años, la función puede regresar el primer año en que se alcanzó la población más alta o cualquier año posterior.

Por ejemplo:

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

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

Además, incluir el Big O de la solución sería útil.

Mi mejor intento de hacer esto sería el siguiente:

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

El algoritmo anterior debería funcionar en tiempo polinómico dado que, en el peor de los O(((n log n) * 2) + k)casos, nes el número de elementos que se ordenarán de cada matriz y el knúmero de años de nacimiento ( ya que sabemos que ksiempre es asík >= y ) dónde yes el número de años de muerte. Sin embargo, no estoy seguro de si hay una solución más eficiente.

Mis intereses están puramente en un Big O mejorado de complejidad computacional sobre el algoritmo existente. La complejidad de la memoria no es motivo de preocupación. Tampoco es la optimización del tiempo de ejecución. Al menos no es una preocupación principal . Cualquier optimización de tiempo de ejecución menor / mayor es bienvenida, pero no es el factor clave aquí.

Creo que podemos tener O(n log n)tiempo con O(1)espacio adicional al ordenar primero, luego mantener una población actual y un máximo global a medida que iteramos. Traté de usar el año actual como punto de referencia, pero la lógica todavía parecía un poco complicada, así que no estoy seguro de que haya funcionado por completo. Con suerte, puede dar una idea del enfoque.

Código JavaScript (contraejemplos / errores bienvenidos)

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

Si el rango de años m, está en el orden de n, podríamos almacenar los conteos para cada año en el rango y tener O(n)una complejidad de tiempo. Si quisiéramos ponernos elegantes, también podríamos tener O(n * log log m)complejidad en el tiempo, mediante el uso de un trie rápido Y que permita la búsqueda del sucesor a O(log log m)tiempo.

Podemos resolver esto en tiempo lineal con la clasificación de cubetas. Digamos que el tamaño de la entrada es n, y el rango de años es m.

O(n): Find the min and max year across births and deaths.
O(m): Create an array of size max_yr - min_yr + 1, ints initialized to zero. 
      Treat the first cell of the array as min_yr, the next as min_yr+1, etc...
O(n): Parse the births array, incrementing the appropriate index of the array. 
      arr[birth_yr - min_yr] += 1
O(n): Ditto for deaths, decrementing the appropriate index of the array.
      arr[death_yr - min_yr] -= 1
O(m): Parse your array, keeping track of the cumulative sum and its max value.

El máximo acumulado más grande es su respuesta.

El tiempo de ejecución es O (n + m), y el espacio adicional necesario es O (m).

Esta es una solución lineal en n si m es O (n); es decir, si el rango de años no está creciendo más rápidamente que el número de nacimientos y muertes. Esto es casi cierto para los datos del mundo real.

Primero agregue los nacimientos y defunciones en un mapa ( year => population change), ordénelo por clave y calcule la población corriente sobre eso.

Esto debería ser aproximadamente O(2n + n log n), donde nes el número de nacimientos.

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

function highestPopulationYear(array $births, array $deaths): ?int
{
    $indexed = [];

    foreach ($births as $birth) {
        $indexed[$birth] = ($indexed[$birth] ?? 0) + 1;
    }

    foreach ($deaths as $death) {
        $indexed[$death] = ($indexed[$death] ?? 0) - 1;
    }

    ksort($indexed);

    $maxYear = null;
    $max = $current = 0;

    foreach ($indexed as $year => $change) {
        $current += $change;
        if ($current >= $max) {
            $max = $current;
            $maxYear = $year;
        }
    }

    return $maxYear;
}

var_dump(highestPopulationYear($births, $deaths));

Resolví este problema con un requisito de memoria de O(n+m)[en el peor de los casos, el mejor de los casos O(n)]

y, complejidad de tiempo de O(n logn).

Aquí, n & mson la longitud de birthsydeaths matrices.

No sé PHP o JavaScript. Lo he implementado con Java y la lógica es muy simple. Pero creo que mi idea también se puede implementar en esos idiomas.

Detalles de la técnica:

Usé la TreeMapestructura Java para almacenar registros de nacimientos y defunciones.

TreeMapinserta datos ordenados ( basados ​​en clave ) como par (clave, valor), aquí la clave es el año y el valor es la suma acumulativa de nacimientos y defunciones (negativo para defunciones).

No necesitamos insertar el valor de muertes que sucedió después del año de nacimiento más alto .

Una vez que TreeMap se llena con los registros de nacimientos y defunciones, todas las sumas acumuladas se actualizan y almacenan la población máxima con el año a medida que avanza.

Entrada y salida de muestra: 1

Births: [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906]

Deaths: [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915]

Year counts Births: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1911=2, 1914=1, 1919=2}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1903=1, 1904=1, 1906=1, 1908=3, 1909=1, 1910=-1, 1911=0, 1912=-1, 1913=-1, 1914=-2, 1915=-2, 1919=2}

Yearwise population: {1900=2, 1901=3, 1903=4, 1904=5, 1906=6, 1908=9, 1909=10, 1910=9, 1911=9, 1912=8, 1913=7, 1914=5, 1915=3, 1919=5}

maxPopulation: 10
yearOfMaxPopulation: 1909

Entrada y salida de muestra: 2

Births: [1906, 1901, 1911, 1902, 1905, 1911, 1902, 1905, 1910, 1912, 1900, 1900, 1904, 1913, 1904]

Deaths: [1917, 1908, 1918, 1915, 1907, 1907, 1917, 1917, 1912, 1913, 1905, 1914]

Year counts Births: {1900=2, 1901=1, 1902=2, 1904=2, 1905=2, 1906=1, 1910=1, 1911=2, 1912=1, 1913=1}

Year counts Birth-Deaths combined: {1900=2, 1901=1, 1902=2, 1904=2, 1905=1, 1906=1, 1907=-2, 1908=-1, 1910=1, 1911=2, 1912=0, 1913=0}

Yearwise population: {1900=2, 1901=3, 1902=5, 1904=7, 1905=8, 1906=9, 1907=7, 1908=6, 1910=7, 1911=9, 1912=9, 1913=9}

maxPopulation: 9
yearOfMaxPopulation: 1906

Aquí, las muertes ocurridas ( 1914 & later) después del último año de nacimiento 1913, no se contaron en absoluto, lo que evita cálculos innecesarios.

Para un total de 10 milliondatos (nacimientos y muertes combinados) y más 1000 years range, el programa tardó 3 sec.en terminar.

Si datos del mismo tamaño con 100 years range, tomó 1.3 sec.

Todas las entradas se toman al azar.

$births = [1984, 1981, 1984, 1991, 1996];
$deaths = [1991, 1984];
$years = array_unique(array_merge($births, $deaths));
sort($years);

$increaseByYear = array_count_values($births);
$decreaseByYear = array_count_values($deaths);
$populationByYear = array();

foreach ($years as $year) {
    $increase = $increaseByYear[$year] ?? 0;
    $decrease = $decreaseByYear[$year] ?? 0;
    $previousPopulationTally = end($populationByYear);
    $populationByYear[$year] = $previousPopulationTally + $increase - $decrease;
}

$maxPopulation = max($populationByYear);
$maxPopulationYears = array_keys($populationByYear, $maxPopulation);

$maxPopulationByYear = array_fill_keys($maxPopulationYears, $maxPopulation);
print_r($maxPopulationByYear);

Esto explicará la posibilidad de un año atado, así como si un año de la muerte de alguien no corresponde al nacimiento de alguien.

En cuanto a la memoria es mantener currentPopulationy currentYearcalcular. Comenzar clasificando ambas $birthsy las $deathsmatrices es un muy buen punto, porque la clasificación de burbujas no es una tarea tan pesada, pero permite cortar algunas esquinas:

<?php

$births = [1997, 1999, 2000];
$deaths = [2000, 2001, 2001];

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

    // sort takes time, but is neccesary for futher optimizations
    sort($births);
    sort($deaths);

    // first death year is a first year where population might decrase 
    // sorfar max population
    $currentYearComputing = $deaths[0];

    // year before first death has potential of having the biggest population
    $maxY = $currentYearComputing-1;

    // calculating population at the begining of the year of first death, start maxPopulation
    $population = $maxPop = count(array_splice($births, 0, array_search($deaths[0], $births)));

    // instead of every time empty checks: `while(!empty($deaths) || !empty($births))`
    // we can control a target time. It reserves a memory, but this slot is decreased
    // every iteration.
    $iterations = count($deaths) + count($births);

    while($iterations > 0) {
        while(current($births) === $currentYearComputing) {
            $population++;
            $iterations--;
            array_shift($births); // decreasing memory usage
        }

        while(current($deaths) === $currentYearComputing) {
            $population--;
            $iterations--;
            array_shift($deaths); // decreasing memory usage
        }

        if ($population > $maxPop) {
            $maxPop = $population;
            $maxY = $currentYearComputing;
        }

        // In $iterations we have a sum of birth/death events left. Assuming all 
        // are births, if this number added to currentPopulation will never exceed
        // current maxPoint, we can break the loop and save some time at cost of
        // some memory.
        if ($maxPop >= ($population+$iterations)) {
            break;
        }

        $currentYearComputing++;
    }

    return $maxY;
}

echo highestPopulationYear($births, $deaths);

no estoy realmente interesado en sumergirse en Big O , te lo dejé a ti.

Además, si redescubre currentYearComputingtodos los bucles, puede cambiar los bucles en ifdeclaraciones y salir con un solo bucle.

    while($iterations > 0) {

        $changed = false;

        if(current($births) === $currentYearComputing) {
            // ...
            $changed = array_shift($births); // decreasing memory usage
        }

        if(current($deaths) === $currentYearComputing) {
            // ...
            $changed = array_shift($deaths); // decreasing memory usage
        }

        if ($changed === false) {
            $currentYearComputing++;
            continue;
        }

Lleno muy cómodo de esta solución, la complejidad Big O es n + m

<?php
function getHighestPopulation($births, $deaths){
    $max = [];
    $currentMax = 0;
    $tmpArray = [];

    foreach($deaths as $key => $death){
        if(!isset($tmpArray[$death])){
            $tmpArray[$death] = 0;    
        }
        $tmpArray[$death]--;
    }
    foreach($births as $k => $birth){
        if(!isset($tmpArray[$birth])){
            $tmpArray[$birth] = 0;
        }
        $tmpArray[$birth]++;
        if($tmpArray[$birth] > $currentMax){
            $max = [$birth];
            $currentMax = $tmpArray[$birth];
        } else if ($tmpArray[$birth] == $currentMax) {
            $max[] = $birth;
        }
    }

    return [$currentMax, $max];
}

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

print_r (getHighestPopulation($births, $deaths));
?>

Uno de los enfoques más simples y claros para su problema.

$births = [1909, 1919, 1904, 1911, 1908, 1908, 1903, 1901, 1914, 1911, 1900, 1919, 1900, 1908, 1906];
$deaths = [1910, 1911, 1912, 1911, 1914, 1914, 1913, 1915, 1914, 1915];

/* for generating 1 million records

for($i=1;$i<=1000000;$i++) {
    $births[] = rand(1900, 2020);
    $deaths[] = rand(1900, 2020);
}
*/

function highestPopulationYear(Array $births, Array $deaths): Int {
    $start_time = microtime(true); 
    $population = array_count_values($births);
    $deaths = array_count_values($deaths);

    foreach ($deaths as $year => $death) {
        $population[$year] = ($population[$year] ?? 0) - $death;
    }
    ksort($population, SORT_NUMERIC);
    $cumulativeSum = $maxPopulation = $maxYear = 0;
    foreach ($population as $year => &$number) {
        $cumulativeSum += $number;
        if($maxPopulation < $cumulativeSum) {
            $maxPopulation = $cumulativeSum;
            $maxYear = $year;
        }
    }
    print " Execution time of function = ".((microtime(true) - $start_time)*1000)." milliseconds"; 
    return $maxYear;
}

print highestPopulationYear($births, $deaths);

salida :

1909

complejidad :

O(m + log(n))