Étant donné deux tableaux; $birthscontenant une liste des années de naissance indiquant quand quelqu'un est né, et $deathscontenant une liste des années de décès indiquant quand quelqu'un est décédé, comment pouvons-nous trouver l'année où la population était la plus élevée?

Par exemple, étant donné les tableaux suivants:

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

L'année où la population était la plus élevée devrait être 1996, car les 3gens étaient en vie au cours de cette année, qui était le nombre de personnes le plus élevé de toutes ces années.

Voici les calculs en cours à ce sujet:

| Naissance | La mort | Population |
| ------- | ------- | ------------ |
| 1981 | | 1 |
| 1984 | | 2 |
| 1984 | 1984 | 2 |
| 1991 | 1991 | 2 |
| 1996 | | 3 |

Hypothèses

Nous pouvons supposer avec certitude que l'année de naissance d'une personne, la population peut augmenter d'une unité et l'année de décès d'une personne, la population peut diminuer d'une unité. Ainsi, dans cet exemple, 2 personnes sont nées en 1984 et 1 personne est décédée en 1984, ce qui signifie que la population a augmenté de 1 cette année-là.

Nous pouvons également supposer en toute sécurité que le nombre de décès ne dépassera jamais le nombre de naissances et qu'aucun décès ne peut survenir lorsque la population est à 0.

Nous pouvons également supposer en toute sécurité que les années dans les deux $deathset $birthsne seront jamais des valeurs négatives ou à virgule flottante ( ce sont toujours des entiers positifs supérieurs à 0 ).

Nous ne pouvons cependant pas supposer que les tableaux seront triés ou qu'il n'y aura pas de valeurs en double, cependant.

Exigences

Nous devons écrire une fonction pour retourner l'année où la population la plus élevée s'est produite, étant donné ces deux tableaux en entrée. La fonction peut retourner 0, false, "", ou NULL( toute valeur de Falsey est acceptable ) si les tableaux d'entrée sont vides ou si la population était toujours à 0 ° C tout au long. Si la population la plus élevée s'est produite sur plusieurs années, la fonction peut renvoyer la première année au cours de laquelle la population la plus élevée a été atteinte ou toute année suivante.

Par exemple:

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

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

De plus, l'inclusion du Big O de la solution serait utile.

Ma meilleure tentative pour ce faire serait la suivante:

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

L'algorithme ci-dessus devrait fonctionner en temps polynomial étant donné qu'il est au pire O(((n log n) * 2) + k)où nest le nombre d'éléments à trier de chaque tableau et kest le nombre d'années de naissance ( car nous savons que kc'est toujoursk >= y ) où yest le nombre d'années de décès. Cependant, je ne sais pas s'il existe une solution plus efficace.

Mes intérêts sont purement dans un Big O amélioré de complexité de calcul sur l'algorithme existant. La complexité de la mémoire n'est pas un problème. L'optimisation de l'exécution n'est pas non plus. Au moins, ce n'est pas une préoccupation principale . Toutes les optimisations d'exécution mineures / majeures sont les bienvenues, mais pas le facteur clé ici.

Je pense que nous pouvons avoir du O(n log n)temps avec de l' O(1)espace supplémentaire en triant d'abord, puis en maintenant une population actuelle et un maximum global pendant que nous itérons. J'ai essayé d'utiliser l'année en cours comme point de référence, mais la logique semblait encore un peu délicate, donc je ne suis pas sûr qu'elle soit complètement réglée. Espérons que cela puisse donner une idée de l'approche.

Code JavaScript (contre-exemples / bugs bienvenus)

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 la plage des années,, mest de l'ordre de n, nous pourrions stocker les chiffres pour chaque année dans la plage et avoir une O(n)complexité temporelle. Si nous voulions devenir fantaisistes, nous pourrions également avoir une O(n * log log m)complexité temporelle, en utilisant un tri rapide Y qui permet une recherche successive dans le O(log log m)temps.

Nous pouvons résoudre ce problème en temps linéaire avec le tri par compartiment. Disons que la taille de l'entrée est n et que la plage d'années est 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.

Le maximum cumulatif le plus élevé est votre réponse.

Le temps de fonctionnement est O (n + m) et l'espace supplémentaire nécessaire est O (m).

Il s'agit d'une solution linéaire dans n si m est O (n); c'est-à-dire, si le nombre d'années ne croît pas plus rapidement que le nombre de naissances et de décès. Cela est presque certainement vrai pour les données du monde réel.

Commencez par regrouper les naissances et les décès sur une carte ( year => population change), triez-les par clé et calculez la population en cours d'exécution.

Cela devrait être approximativement O(2n + n log n), où nest le nombre de naissances.

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

J'ai résolu ce problème avec une mémoire requise O(n+m)[dans le pire des cas, dans le meilleur des cas O(n)]

et la complexité temporelle de O(n logn).

Voici n & mla longueur birthset les deathstableaux.

Je ne connais pas PHP ou javascript. Je l'ai implémenté avec Java et la logique est très simple. Mais je crois que mon idée peut également être implémentée dans ces langues.

Détails techniques:

J'ai utilisé la TreeMapstructure java pour stocker les enregistrements de naissances et de décès.

TreeMapinsère des données triées ( basées sur les clés ) sous forme de paire (clé, valeur), ici la clé est l'année et la valeur est la somme cumulée des naissances et des décès (négatif pour les décès).

Nous n'avons pas besoin d'insérer la valeur des décès survenus après l' année de naissance la plus élevée .

Une fois que TreeMap est rempli avec les enregistrements de naissances et de décès, toutes les sommes cumulées sont mises à jour et stockent la population maximale avec l'année au fur et à mesure de sa progression.

Exemple d'entrée et de sortie: 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

Exemple d'entrée et de sortie: 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

Ici, les décès survenus ( 1914 & later) après la dernière année de naissance 1913, n'ont pas été comptés du tout, ce qui évite les calculs inutiles.

Pour un total de 10 milliondonnées (naissances et décès combinés) et plus 1000 years range, le programme a pris sur le point 3 sec.de se terminer.

Si des données de même taille avec 100 years range, il a fallu 1.3 sec.

Toutes les entrées sont prises au hasard.

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

Cela tiendra compte de la possibilité d'une année liée, ainsi que si une année de décès d'une personne ne correspond pas à la naissance d'une personne.

En termes de mémoire, il est à conserver currentPopulationet à currentYearcalculer. Commencer par trier les deux $birthset les $deathstableaux est un très bon point, car le tri à bulles n'est pas une tâche si lourde, mais permet de couper certains coins:

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

pas vraiment envie de plonger dans Big O , laissez-le vous.

De plus, si vous redécouvrez currentYearComputingchaque boucle, vous pouvez changer les boucles en ifinstructions et partir avec une seule boucle.

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

Je remplis très à l'aise cette solution, la complexité Big O est 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));
?>

L'une des approches les plus simples et les plus claires pour votre problème.

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

sortie :

1909

complexité :

O(m + log(n))