Biorąc pod uwagę dwie tablice; $birthszawierający listę lat urodzenia wskazującą, kiedy ktoś się urodził, oraz $deathslistę lat śmierci wskazującą, kiedy ktoś umarł, w jaki sposób możemy znaleźć rok, w którym populacja była najwyższa?

Na przykład biorąc pod uwagę następujące tablice:

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

Powinien być rok, w którym populacja była najwyższa 1996, ponieważ 3ludzie żyli w tym roku, który był najwyższą liczbą ludności we wszystkich tych latach.

Oto bieżąca matematyka na ten temat:

| Narodziny | Śmierć | Ludność |
| ------- | ------- | ------------ |
| 1981 | | 1 |
| 1984 | | 2 |
| 1984 | 1984 | 2 |
| 1991 | 1991 | 2 |
| 1996 | | 3 |

Założenia

Możemy bezpiecznie założyć, że rok, w którym ktoś się urodzi, populacja może wzrosnąć o jeden rok, a rok, w którym ktoś umrze, populacja może się zmniejszyć o jeden. W tym przykładzie 2 osoby urodziły się w 1984 r., A 1 osoba zmarła w 1984 r., Co oznacza, że ​​liczba ludności wzrosła o 1 w tym roku.

Możemy również bezpiecznie założyć, że liczba zgonów nigdy nie przekroczy liczby urodzeń i że śmierć nie może wystąpić, gdy populacja wynosi 0.

Możemy również bezpiecznie założyć, że lata w obu przypadkach $deathsi $birthsnigdy nie będą wartościami ujemnymi lub zmiennoprzecinkowymi ( zawsze są dodatnimi liczbami całkowitymi większymi niż 0 ).

Nie możemy jednak zakładać, że tablice zostaną posortowane lub że nie będzie zduplikowanych wartości.

Wymagania

Musimy napisać funkcję zwracającą rok, w którym wystąpiła najwyższa populacja, biorąc pod uwagę te dwie tablice jako dane wejściowe. Funkcja może powrócić 0, false, ""lub NULL( każda wartość falsey jest dopuszczalna ), gdy tablice wejściowe są puste czy populacja zawsze w 0 ° C przez cały czas. Jeśli najwyższa populacja występowała przez wiele lat, funkcja może powrócić do pierwszego roku, w którym osiągnięto najwyższą populację, lub dowolnego następnego roku.

Na przykład:

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

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

Dodatkowo pomocne byłoby włączenie Big O rozwiązania.

Moja najlepsza próba zrobienia tego to:

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

Powyższy algorytm powinien działać w czasie wielomianowym, biorąc pod uwagę, że w najgorszym O(((n log n) * 2) + k)przypadku njest to liczba elementów do posortowania z każdej tablicy i kliczba lat urodzenia ( ponieważ wiemy, że tak kjest zawszek >= y ), gdzie yjest liczba lat śmierci. Nie jestem jednak pewien, czy istnieje bardziej wydajne rozwiązanie.

Moje zainteresowania skupiają się wyłącznie na ulepszonym Big O złożoności obliczeniowej w stosunku do istniejącego algorytmu. Złożoność pamięci nie ma znaczenia. Nie jest też optymalizacja środowiska wykonawczego. Przynajmniej nie jest to główny problem . Wszelkie drobne / większe optymalizacje środowiska wykonawczego są mile widziane, ale nie są to kluczowe czynniki.

Myślę, że możemy mieć O(n log n)czas na O(1)dodatkowe miejsce, najpierw sortując, a następnie utrzymując bieżącą populację i globalne maksimum podczas iteracji. Starałem się wykorzystać bieżący rok jako punkt odniesienia, ale logika nadal wydawała się nieco trudna, więc nie jestem pewien, czy to się udało. Mamy nadzieję, że da to wyobrażenie o tym podejściu.

Kod JavaScript (mile widziane kontrprzykłady / błędy)

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

Jeśli zakres roku m, jest rzędu n, moglibyśmy przechowywać liczby dla każdego roku w tym przedziale i mieć O(n)złożoność czasową. Gdybyśmy chcieli się zachwycić, moglibyśmy również mieć O(n * log log m)złożoność czasową, używając szybkiej wersji Y, która umożliwia wyszukiwanie następcy w O(log log m)czasie.

Możemy to rozwiązać w czasie liniowym za pomocą sortowania kubełkowego. Powiedzmy, że rozmiar danych wejściowych wynosi n, a zakres lat to 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.

Największa skumulowana wartość maksymalna jest odpowiedzią.

Czas działania wynosi O (n + m), a potrzebna dodatkowa przestrzeń to O (m).

Jest to rozwiązanie liniowe w n, jeżeli m oznacza O (n); tzn. jeśli zakres lat nie rośnie szybciej niż liczba urodzeń i zgonów. Jest to prawie na pewno prawdziwe w przypadku danych z prawdziwego świata.

Najpierw zbierz year => population changeliczbę urodzeń i zgonów w mapę ( ), posortuj je według klucza i oblicz na tej podstawie populację.

Powinno to być w przybliżeniu O(2n + n log n), gdzie njest liczba urodzeń.

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

Rozwiązałem ten problem wymagając pamięci O(n+m)[w najgorszym przypadku, najlepszym przypadku O(n)]

oraz złożoność czasowa O(n logn).

Oto n & mdługość birthsideaths tablice.

Nie znam PHP ani javascript. Zaimplementowałem to w Javie, a logika jest bardzo prosta. Ale wierzę, że mój pomysł można również wdrożyć w tych językach.

Szczegóły techniki:

Użyłem TreeMapstruktury java do przechowywania akt narodzin i zgonów.

TreeMapwstawia dane posortowane (na podstawie klucza ) jako parę (klucz, wartość), tutaj klucz to rok, a wartość to łączna suma urodzeń i zgonów (ujemna dla zgonów).

Nie musimy wstawiać wartości zgonów, które miały miejsce po najwyższym roku urodzenia.

Gdy TreeMap zostanie zapełniony rekordami urodzeń i zgonów, wszystkie skumulowane sumy są aktualizowane i przechowują maksymalną populację wraz z rokiem w miarę postępu.

Przykładowe wejście i wyjście: 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

Przykładowe wejście i wyjście: 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

Tutaj zgony wystąpiły ( 1914 & later) po ostatnim roku urodzenia 1913, w ogóle nie zostały policzone, co pozwala uniknąć niepotrzebnych obliczeń.

Program obejmował łącznie wszystkie 10 milliondane (narodziny i zgony łącznie) i więcej .1000 years range3 sec.

Jeśli dane o 100 years rangetym samym rozmiarze z , zajęło 1.3 sec.

Wszystkie dane wejściowe są pobierane losowo.

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

Uwzględni to możliwość związania roku, a także tego, czy rok śmierci innej osoby nie odpowiada urodzeniu kogoś.

Jeśli chodzi o pamięć, należy ją zachować currentPopulationi currentYearobliczyć. Rozpoczynanie od sortowania zarówno tablic, jak $birthsi $deathstablic, jest bardzo dobrym punktem, ponieważ sortowanie bąbelków nie jest tak trudnym zadaniem, ale pozwala wyciąć niektóre rogi:

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

nie bardzo lubię nurkować w Big O , zostawiłem to tobie.

Ponadto, jeśli ponownie odkryjesz currentYearComputingkażdą pętlę, możesz zamienić pętle na ifinstrukcje i wyjść z tylko jedną pętlą.

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

Wypełniam bardzo wygodnie to rozwiązanie, złożoność Big O wynosi 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));
?>

Jedno z najprostszych i najbardziej przejrzystych rozwiązań dla twojego problemu.

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

wyjście :

1909

złożoność :

O(m + log(n))