Diberikan dua array; $birthsberisi daftar tahun kelahiran yang menunjukkan kapan seseorang dilahirkan, dan $deathsberisi daftar tahun kematian yang menunjukkan kapan seseorang meninggal, bagaimana kita dapat menemukan tahun di mana populasi tertinggi?

Misalnya diberikan array berikut:

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

Tahun di mana populasi tertinggi seharusnya 1996, karena 3orang-orang hidup selama tahun itu, yang merupakan jumlah populasi tertinggi sepanjang tahun itu.

Inilah perhitungannya:

| Kelahiran | Kematian | Populasi |
| ------- | ------- | ------------ |
| 1981 | | 1 |
| 1984 | | 2 |
| 1984 | 1984 | 2 |
| 1991 | 1991 | 2 |
| 1996 | | 3 |

Asumsi

Kita dapat dengan aman berasumsi bahwa tahun di mana seseorang dilahirkan populasi dapat meningkat satu dan tahun di mana seseorang meninggal populasi dapat berkurang satu. Jadi, dalam contoh ini, 2 orang lahir pada tahun 1984 dan 1 orang meninggal pada tahun 1984, artinya populasi meningkat 1 pada tahun itu.

Kita juga dapat dengan aman berasumsi bahwa jumlah kematian tidak akan pernah melebihi jumlah kelahiran dan bahwa tidak ada kematian dapat terjadi ketika populasi berada pada 0.

Kita juga dapat dengan aman mengasumsikan bahwa tahun-tahun di keduanya $deathsdan $birthstidak akan pernah menjadi nilai negatif atau floating point ( mereka selalu bilangan bulat positif lebih besar dari 0 ).

Kami tidak dapat berasumsi bahwa array akan diurutkan atau tidak akan ada nilai duplikat.

Persyaratan

Kita harus menulis fungsi untuk mengembalikan tahun di mana populasi tertinggi terjadi, mengingat dua array ini sebagai input. Fungsi dapat kembali 0, false, "", atau NULL( nilai apapun falsey diterima ) jika array masukan kosong atau jika populasi selalu pada 0 seluruh. Jika populasi tertinggi terjadi pada beberapa tahun, fungsi dapat mengembalikan tahun pertama di mana populasi tertinggi dicapai atau tahun berikutnya.

Sebagai contoh:

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

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

Selain itu, termasuk Big O dari solusi akan sangat membantu.

Upaya terbaik saya untuk melakukan ini adalah sebagai berikut:

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

Algoritma di atas harus bekerja dalam waktu polinomial mengingat paling buruk di O(((n log n) * 2) + k)mana njumlah elemen yang akan diurutkan dari setiap array dan kjumlah tahun kelahiran ( karena kita tahu itu kselaluk >= y ) di mana yjumlah tahun kematian. Namun, saya tidak yakin apakah ada solusi yang lebih efisien.

Minat saya murni pada perbaikan kompleksitas komputasi pada algoritma yang ada. Kompleksitas memori tidak menjadi masalah. Optimasi runtime juga tidak. Setidaknya itu bukan masalah utama . Semua optimasi runtime minor / utama disambut baik, tetapi bukan faktor kunci di sini.

Saya pikir kita dapat memiliki O(n log n)waktu dengan O(1)ruang tambahan dengan menyortir terlebih dahulu, kemudian mempertahankan populasi saat ini dan maksimum global seperti yang kita lakukan. Saya mencoba menggunakan tahun ini sebagai titik referensi tetapi logikanya masih tampak sedikit rumit jadi saya tidak yakin itu benar-benar berhasil. Semoga bisa memberi gambaran tentang pendekatannya.

Kode JavaScript (welcome counterexamples / bug)

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

Jika rentang tahun m,, berada di urutan n, kita dapat menyimpan jumlah untuk setiap tahun dalam rentang dan memiliki O(n)kompleksitas waktu. Jika kita ingin mendapatkan kemewahan, kita juga bisa memiliki O(n * log log m)kompleksitas waktu, dengan menggunakan trie Y-fast yang memungkinkan pencarian pengganti dalam O(log log m)waktu.

Kita dapat menyelesaikan ini dalam waktu linier dengan semacam ember. Katakanlah ukuran input adalah n, dan rentang tahun adalah 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.

Maksimum kumulatif terbesar adalah jawaban Anda.

Waktu berjalan adalah O (n + m), dan ruang tambahan yang dibutuhkan adalah O (m).

Ini adalah solusi linier dalam n jika m adalah O (n); yaitu, jika rentang tahun tidak tumbuh lebih cepat daripada jumlah kelahiran dan kematian. Ini hampir pasti benar untuk data dunia nyata.

Pertama agregat kelahiran dan kematian ke dalam peta ( year => population change), urutkan berdasarkan kunci, dan hitung populasi yang berjalan di atasnya.

Ini harus kira-kira O(2n + n log n), di mana njumlah kelahiran.

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

Saya memecahkan masalah ini dengan persyaratan memori O(n+m)[dalam kasus terburuk, kasus terbaik O(n)]

dan, kompleksitas waktu O(n logn).

Di sini, n & madalah panjang birthsdan deathsarray.

Saya tidak tahu PHP atau javascript. Saya sudah mengimplementasikannya dengan Java dan logikanya sangat sederhana. Tapi saya percaya ide saya dapat diimplementasikan dalam bahasa-bahasa itu juga

Detail Teknik:

Saya menggunakan TreeMapstruktur java untuk menyimpan catatan kelahiran dan kematian.

TreeMapmemasukkan data yang diurutkan ( berbasis kunci ) sebagai pasangan (kunci, nilai), di sini kunci adalah tahun dan nilainya adalah jumlah kumulatif dari kelahiran & kematian (negatif untuk kematian).

Kita tidak perlu memasukkan nilai kematian yang terjadi setelah tahun kelahiran tertinggi .

Setelah TreeMap diisi dengan catatan kelahiran & kematian, semua jumlah kumulatif diperbarui dan menyimpan populasi maksimum dengan tahun seiring kemajuan.

Contoh input & output: 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

Contoh input & output: 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

Di sini, kematian terjadi ( 1914 & later) setelah tahun kelahiran terakhir 1913, tidak dihitung sama sekali, yang menghindari perhitungan yang tidak perlu.

Untuk total 10 milliondata (kombinasi kelahiran & kematian) dan yang lebih 1000 years range, program ini akan 3 sec.selesai.

Jika ukuran data sama dengan 100 years range, butuh 1.3 sec.

Semua input diambil secara acak.

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

Ini akan menjelaskan kemungkinan tahun terikat, serta jika satu tahun kematian seseorang tidak sesuai dengan kelahiran seseorang.

Memori bijaksana untuk menjaga currentPopulationdan currentYearmenghitung. Memulai dengan menyortir keduanya $birthsdan $deathsarray adalah hal yang sangat baik, karena bubble sorting bukanlah tugas yang berat, namun memungkinkan untuk memotong beberapa sudut:

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

tidak benar-benar tertarik untuk menyelam ke hal Big O , serahkan pada Anda.

Juga, jika Anda menemukan kembali currentYearComputingsetiap loop, Anda dapat mengubah loop menjadi ifpernyataan dan pergi hanya dengan satu loop.

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

Saya mengisi solusi ini sangat nyaman, kompleksitas Big O adalah 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));
?>

Salah satu pendekatan paling sederhana dan jelas untuk masalah Anda.

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

keluaran :

1909

kompleksitas :

O(m + log(n))