Minimum Platforms

Q: Berapa kompleksitas waktu dari masalah jumlah minimum peron?

Mengurutkan kedua array membutuhkan O(n log n) , dan penelusuran setelahnya membutuhkan O(n) , jadi pengurutan mendominasi. Salinan yang sudah diurutkan membutuhkan ruang tambahan O(n) .

Q: Apa perbedaan minimum platforms dengan meeting rooms II?

Keduanya meminta jumlah interval terbanyak yang saling tumpang tindih pada satu waktu. Di sini, kereta tetap menempati peronnya hingga menit keberangkatannya; dalam meeting rooms II, ruangan kosong tepat saat rapatnya berakhir. Dalam proses sweep, hal itu ditentukan oleh satu perbandingan: jika waktunya sama, proses kedatangan lebih dahulu di sini, dan rapat yang berakhir lebih dahulu di sana.

Q: Apakah masalah platform minimum dapat diselesaikan tanpa pengurutan?

Ya, karena setiap waktu sesuai dengan jam yang tetap. Gunakan 2401 penghitung dengan indeks berupa angka HHMM , tambahkan 1 pada setiap kedatangan dan kurangi 1 pada departure + 1 . Jumlah berjalan terbesar adalah jawabannya: waktu O(n + 2400) . Indeks seperti 1260 hingga 1299 bukan waktu pada jam dan tidak mendapat kedatangan, jadi tidak pernah menghasilkan puncak.

SedangPengurutan Greedy Two pointers

+10

Sebuah stasiun memiliki jadwal kereta untuk satu hari: kereta i tiba pada arrival[i] dan berangkat pada departure[i]. Waktu ditulis sebagai angka HHMM, yaitu waktu tanpa tanda titik dua, jadi 930 berarti pukul 09:30.

Sebuah kereta menggunakan peronnya sejak menit kedatangannya hingga menit keberangkatannya, termasuk kedua menit tersebut. Jadi, kereta yang tiba pada menit yang sama saat kereta lain berangkat tidak dapat menggunakan peron kereta tersebut.

Kembalikan jumlah peron paling sedikit yang dibutuhkan stasiun agar tidak ada kereta yang harus menunggu.

Fungsi

minimumPlatforms(arrival: integer-array, departure: integer-array) → integer

arrivalinteger-array: waktu kedatangan setiap kereta, dalam bentuk angka HHMM
departureinteger-array: waktu keberangkatan setiap kereta, dalam bentuk angka HHMM; departure[i] berpasangan dengan arrival[i]
Mengembalikaninteger: jumlah kereta terbanyak di stasiun pada menit yang sama, yaitu jumlah peron paling sedikit yang dibutuhkan

Batasan

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Setiap waktu adalah waktu HHMM yang valid: dua digit terakhirnya paling banyak 59.
Semua kereta berjalan pada hari yang sama. Array-array tersebut tidak diurutkan.

Contoh

Input: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Output: 3
Penjelasan: Pada pukul 15:30, tiga kereta berada di stasiun: kereta dari pukul 15:00 sampai 16:00, dari pukul 15:20 sampai 15:35, dan dari pukul 15:30 sampai 15:45. Tidak ada menit saat ada empat kereta, jadi 3 peron sudah cukup.

Input: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Output: 2
Penjelasan: Kereta yang tiba pukul 12:30 bertemu dengan kereta yang berangkat pukul 12:30, dan hal yang sama terjadi pukul 13:00. Pada masing-masing waktu tersebut, ada dua kereta di stasiun, jadi jawabannya adalah 2, bukan 1.

Input: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Output: 2
Penjelasan: Kereta dari pukul 06:00 sampai 22:00 membuat satu peron sibuk sepanjang hari. Kereta dari pukul 07:00 sampai 07:15 dan dari pukul 13:00 sampai 14:00 tidak pernah bertemu, jadi keduanya berbagi peron kedua: 2.

Pertanyaan lanjutan

Beberapa kereta malam tiba sebelum tengah malam dan berangkat setelahnya, sehingga nomor keberangkatannya lebih kecil daripada nomor kedatangannya. Bagaimana cara menghitung peron ketika jadwal melewati tengah malam?

Solusi

Jawabannya adalah jumlah kereta terbanyak di stasiun pada menit yang sama. Tugasnya adalah menemukan menit tersibuk itu tanpa membandingkan setiap pasangan kereta. Urutkan waktu kedatangan dan keberangkatan secara terpisah, lalu telusuri peristiwa sepanjang hari satu kali sambil menghitung jumlah kereta yang sedang berada di stasiun untuk menemukannya dalam O(n log n).

Hitung jumlah kereta di setiap kedatangan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Kereta yang berada di stasiun pada menit yang sama membutuhkan peron yang berbeda, jadi menit tersibuk menjadi batas bawah. Jumlah itu juga cukup: buka peron baru hanya ketika kereta yang tiba mendapati semua peron yang sudah dibuka sedang terisi. Pada menit itu, ada kereta di setiap peron yang sudah dibuka, ditambah kereta baru, jadi kamu tidak pernah membuka lebih banyak peron daripada jumlah puncaknya.

Jumlah kereta yang ada hanya bertambah saat kereta tiba, jadi menit tersibuk adalah menit kedatangan suatu kereta. Untuk setiap kereta i, hitung kereta j yang memenuhi arrival[j] ≤ arrival[i] ≤ departure[j]. Kedua perbandingan menggunakan ≤ karena kereta masih berada di peronnya pada menit keberangkatannya.

Setiap satu dari n kereta memeriksa semua n kereta, jadi waktu komputasinya adalah O(n²): 25 juta pemeriksaan pasangan untuk 5000 kereta.

Algoritma

Tetapkan most = 0.
Untuk setiap kereta i, hitung kereta j dengan arrival[j] ≤ arrival[i] ≤ departure[j].
Jika jumlah itu lebih besar daripada most, simpan jumlah tersebut.
Kembalikan most.

def minimumPlatforms(arrival, departure):
    n = len(arrival)
    most = 0
    for i in range(n):
        # trains standing at the station in the minute train i arrives
        here = 0
        for j in range(n):
            if arrival[j] <= arrival[i] <= departure[j]:
                here += 1
        most = max(most, here)
    return most

Urutkan kedua list dan telusuri dengan dua pointer

Intuisi

Jumlah kereta yang ada hanya bergantung pada berapa banyak kereta yang telah tiba dan berapa banyak yang telah berangkat pada menit tertentu, bukan pada kereta mana yang berangkat kapan. Jadi, urutkan waktu kedatangan dan waktu keberangkatan sebagai dua list yang terpisah. Jika dibaca sesuai urutan waktu, keduanya menjadi peristiwa hari itu: kedatangan menambah satu kereta, keberangkatan mengurangi satu kereta.

Jika waktunya sama, kedatangan dihitung lebih dulu, karena kereta yang akan berangkat masih menggunakan peronnya pada menit itu. Pada contoh pertama, jumlahnya kembali menjadi 0 setelah keberangkatan pukul 1100, lalu kedatangan pukul 1500, 1520, dan 1530 semuanya terjadi sebelum keberangkatan pukul 1535, sehingga jumlahnya mencapai 3.

Setelah semua kedatangan selesai, keberangkatan yang tersisa hanya dapat mengurangi jumlah kereta, jadi prosesnya berhenti di sana. Pengurutan memerlukan O(n log n) dan prosesnya membutuhkan paling banyak 2n langkah.

Algoritma

Urutkan salinan arrival dan salinan departure.
Atur platforms, most, i, dan j ke 0.
Selama i < n: jika arrivals[i] ≤ departures[j], tambahkan 1 ke platforms, perbarui most, lalu lanjutkan i.
Jika tidak, kurangi 1 dari platforms, lalu lanjutkan j.
Kembalikan most.

def minimumPlatforms(arrival, departure):
    arrivals = sorted(arrival)
    departures = sorted(departure)
    n = len(arrivals)
    platforms = 0  # trains at the station right now
    most = 0
    i = 0  # next arrival
    j = 0  # next departure
    while i < n:
        if arrivals[i] <= departures[j]:
            # the next event is an arrival; on a tie the leaving train is still there
            platforms += 1
            most = max(most, platforms)
            i += 1
        else:
            platforms -= 1
            j += 1
    return most

Jebakan dan kasus tepi

Membandingkan dengan < saat aturan inklusif memerlukan ≤. Pada contoh kedua, setiap kereta yang tiba kemudian menggunakan peron kereta yang berangkat pada menit itu, sehingga jawabannya turun dari 2 menjadi 1.
Mengurangi angka HHMM: 1300 dikurangi 1259 hasilnya 41, padahal waktunya berselisih satu menit. Membandingkannya aman, dan solusi hanya melakukan perbandingan.
Mengurutkan kereta berdasarkan waktu kedatangan lalu membandingkan masing-masing hanya dengan kereta sebelumnya. Waktu singgah yang lama, seperti pukul 06:00 hingga 22:00 pada contoh ketiga, bertumpang tindih dengan kereta yang berada jauh di bagian bawah daftar.
Melewatkan kereta yang tiba dan berangkat pada menit yang sama. Empat kereta yang masing-masing berhenti dari pukul 10:00 hingga 10:00 memerlukan empat peron.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu dari masalah jumlah minimum peron?

Mengurutkan kedua array membutuhkan O(n log n), dan penelusuran setelahnya membutuhkan O(n), jadi pengurutan mendominasi. Salinan yang sudah diurutkan membutuhkan ruang tambahan O(n).

Apa perbedaan minimum platforms dengan meeting rooms II?

Keduanya meminta jumlah interval terbanyak yang saling tumpang tindih pada satu waktu. Di sini, kereta tetap menempati peronnya hingga menit keberangkatannya; dalam meeting rooms II, ruangan kosong tepat saat rapatnya berakhir. Dalam proses sweep, hal itu ditentukan oleh satu perbandingan: jika waktunya sama, proses kedatangan lebih dahulu di sini, dan rapat yang berakhir lebih dahulu di sana.

Apakah masalah platform minimum dapat diselesaikan tanpa pengurutan?

Ya, karena setiap waktu sesuai dengan jam yang tetap. Gunakan 2401 penghitung dengan indeks berupa angka HHMM, tambahkan 1 pada setiap kedatangan dan kurangi 1 pada departure + 1. Jumlah berjalan terbesar adalah jawabannya: waktu O(n + 2400). Indeks seperti 1260 hingga 1299 bukan waktu pada jam dan tidak mendapat kedatangan, jadi tidak pernah menghasilkan puncak.

def minimumPlatforms(arrival, departure):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

arrival = [900, 1500, 920, 1520, 1000, 1530]
departure = [930, 1600, 1010, 1535, 1100, 1545]

Output yang diharapkan