Minimum Platforms

Q: Minimum platformlar probleminin zaman karmaşıklığı nedir?

İki diziyi sıralamak O(n log n) maliyetindedir ve ardından yapılan tarama O(n) maliyetindedir; dolayısıyla baskın maliyet sıralamalardır. Sıralanmış kopyalar O(n) ek alan kullanır.

Q: Minimum platform sayısı, Meeting Rooms II probleminden nasıl farklıdır?

İkisi de tek bir anda çakışan en fazla sayıda aralığı sorar. Burada bir tren, ayrıldığı dakika boyunca peronunu işgal eder; Meeting Rooms II'de ise bir oda, toplantısı biter bitmez boşalır. Tarama sırasında bu, tek bir karşılaştırmadır: eşitlik durumunda burada önce varışı, orada ise önce biten toplantıyı işlersin.

Q: Minimum platform sayısı sıralama yapılmadan bulunabilir mi?

Evet, çünkü her zaman dilimi sabit bir saate karşılık gelir. 2401 sayacı HHMM numarasına göre indeksle, her varışta 1 ekle ve departure + 1 noktasında 1 çıkar. En büyük kümülatif toplam yanıttır: O(n + 2400) zaman. 1260 ile 1299 arasındaki indeksler gibi değerler saat değildir ve bunlara varış olmaz; bu nedenle hiçbir zaman zirve oluşturmazlar.

OrtaSıralama Açgözlü İki işaretçi

+10

Bir istasyonun bir günlük tarifesi vardır: i numaralı tren arrival[i] saatinde gelir ve departure[i] saatinde ayrılır. Saatler HHMM biçimindedir; iki nokta işareti olmadan saat gösterilir, bu nedenle 930, 09:30 anlamına gelir.

Bir tren, geldiği dakikadan ayrıldığı dakikaya kadar, her iki dakika da dahil olmak üzere, peronunu kullanır. Bu nedenle, başka bir trenin ayrıldığı dakika gelen bir tren o trenin peronunu kullanamaz.

Hiçbir trenin beklemesi gerekmemesi için istasyonun ihtiyaç duyduğu en az peron sayısını döndürün.

Fonksiyon

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

arrivalinteger-array: her trenin varış saati, HHMM biçiminde bir sayı
departureinteger-array: her trenin HHMM biçimindeki hareket saati; departure[i], arrival[i] ile eşleşir
Döndürürinteger: aynı dakikada istasyondaki en fazla tren sayısı; gereken en az platform sayısı da budur

Kısıtlar

1 ≤ arrival.length == departure.length ≤ 5000
0 ≤ arrival[i] ≤ departure[i] ≤ 2359
Her zaman, son iki basamağı en fazla 59 olan geçerli bir HHMM saatidir.
Tüm trenler aynı gün çalışır. Diziler sıralı değildir.

Örnekler

Girdi: arrival = [900, 1500, 920, 1520, 1000, 1530]departure = [930, 1600, 1010, 1535, 1100, 1545]
Çıktı: 3
Açıklama: 15:30'da istasyonda üç tren duruyor: 15:00–16:00, 15:20–15:35 ve 15:30–15:45 seferleri. Hiçbir dakikada dört tren olmuyor, bu yüzden 3 peron yeterli.

Girdi: arrival = [1200, 1230, 1300]departure = [1230, 1300, 1315]
Çıktı: 2
Açıklama: 12:30'da gelen tren, 12:30'da kalkan trenle buluşur; aynı durum 13:00'te de yaşanır. Bu dakikaların her birinde istasyonda iki tren vardır, bu nedenle cevap 1 değil, 2'dir.

Girdi: arrival = [600, 700, 1300]departure = [2200, 715, 1400]
Çıktı: 2
Açıklama: 06:00 ile 22:00 arasındaki tren bütün gün bir peronu meşgul tutar. 07:00-07:15 ve 13:00-14:00 saatleri arasındaki trenler hiç karşılaşmadığından ikinci bir peronu paylaşırlar: 2.

Ek soru

Gece trenlerinden bazıları gece yarısından önce gelir ve gece yarısından sonra hareket eder; bu nedenle hareket saatleri varış saatlerinden daha küçüktür. Tarife gece yarısını aştığında peronları nasıl sayarsınız?

Çözüm

Yanıt, aynı dakika içinde istasyonda bulunan en fazla tren sayısıdır. Yapılması gereken, her tren çiftini karşılaştırmadan en yoğun dakikayı bulmaktır. Varışları ve ayrılışları ayrı ayrı sıralayın; ardından günün olayları boyunca mevcut sayıyı güncel tutarak bir kez ilerlemek, bu dakikayı O(n log n) sürede bulur.

Her varış noktasındaki trenleri say

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Aynı dakika içinde duran trenlerin her biri farklı bir perona ihtiyaç duyar; bu yüzden en yoğun dakika alt sınırı belirler. Bu sayı aynı zamanda yeterlidir: Gelen bir tren, açık olan tüm peronları dolu bulduğunda yeni bir peron aç. O dakikada her açık peronda ve yeni peronda bir tren durur; böylece en yoğun dakikadaki sayıdan fazla peron açmazsın.

Mevcut tren sayısı yalnızca bir tren geldiğinde artar; dolayısıyla en yoğun dakika, bir trenin varış dakikasıdır. Her tren i için, arrival[j] ≤ arrival[i] ≤ departure[j] koşulunu sağlayan trenlerin j sayısını bul. Her iki karşılaştırmada da ≤ kullanılır; çünkü bir tren ayrıldığı dakika boyunca hâlâ peronunda durur.

n trenin her biri n trenin tamamını kontrol eder; bu nedenle işlem sayısı O(n²) olur: 5000 tren için 25 milyon çift kontrolü.

Algoritma

most = 0 olarak ayarla.
Her bir i treni için, arrival[j] ≤ arrival[i] ≤ departure[j] koşulunu sağlayan j trenlerini say.
Bu sayı most değerinden büyükse, bu sayıyı kaydet.
most değerini döndür.

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

Her iki listeyi de sıralayın ve iki işaretçiyle tarayın

Sezgi

Mevcut tren sayısı, hangi trenin ne zaman ayrıldığına değil, belirli bir dakikaya kadar kaç trenin geldiğine ve kaçının ayrıldığına bağlıdır. Bu yüzden varış saatlerini ve ayrılış saatlerini birbirinden bağımsız iki liste olarak sıralayın. Zaman sırasına göre birlikte okunduklarında günün olaylarını oluştururlar: bir varış tren sayısını artırır, bir ayrılış ise azaltır.

Eşitlik durumunda önce varış gelir, çünkü ayrılan tren o dakika boyunca peronunu kullanmaya devam eder. İlk örnekte, 1100'deki ayrılıştan sonra sayı yeniden 0 olur; ardından 1500, 1520 ve 1530'daki varışların tümü 1535'teki ayrılıştan önce gerçekleşir ve sayı 3'e ulaşır.

Varışlar tükendiğinde, geriye kalan ayrılışlar sayıyı yalnızca azaltabilir; bu yüzden işlem orada durur. Sıralama O(n log n) maliyetlidir ve işlem en fazla 2n adım sürer.

Algoritma

arrival öğesinin bir kopyasını ve departure öğesinin bir kopyasını sıralayın.
platforms, most, i ve j değerlerini 0 olarak ayarlayın.
i < n olduğu sürece: arrivals[i] ≤ departures[j] ise platforms değerini 1 artırın, most değerini güncelleyin ve i değerini ilerletin.
Aksi takdirde platforms değerini 1 azaltın ve j değerini ilerletin.
most değerini döndürün.

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

Tuzaklar ve uç durumlar

Kapsayıcı kuralın ≤ gerektirdiği yerde < ile karşılaştırmak. İkinci örnekte o dakika gelen her tren, o dakika ayrılan trenin peronunu alır ve cevap 2'den 1'e düşer.
HHMM sayılarını çıkarmak: 1300 eksi 1259, 41 eder; oysa saatler arasında bir dakika vardır. Bunları karşılaştırmak güvenlidir ve çözüm yalnızca karşılaştırma yapar.
Trenleri varış saatlerine göre sıralamak ve her birini yalnızca kendinden önceki trenle karşılaştırmak. Üçüncü örnekte 06:00'dan 22:00'ye kadar süren uzun bir konaklama, listenin çok ilerisindeki trenlerle çakışır.
Aynı dakika içinde gelip ayrılan trenleri atlamak. Her biri 10:00'dan 10:00'ye kadar bekleyen dört tren için dört peron gerekir.

Sıkça sorulan sorular3

Minimum platformlar probleminin zaman karmaşıklığı nedir?

İki diziyi sıralamak O(n log n) maliyetindedir ve ardından yapılan tarama O(n) maliyetindedir; dolayısıyla baskın maliyet sıralamalardır. Sıralanmış kopyalar O(n) ek alan kullanır.

Minimum platform sayısı, Meeting Rooms II probleminden nasıl farklıdır?

İkisi de tek bir anda çakışan en fazla sayıda aralığı sorar. Burada bir tren, ayrıldığı dakika boyunca peronunu işgal eder; Meeting Rooms II'de ise bir oda, toplantısı biter bitmez boşalır. Tarama sırasında bu, tek bir karşılaştırmadır: eşitlik durumunda burada önce varışı, orada ise önce biten toplantıyı işlersin.

Minimum platform sayısı sıralama yapılmadan bulunabilir mi?

Evet, çünkü her zaman dilimi sabit bir saate karşılık gelir. 2401 sayacı HHMM numarasına göre indeksle, her varışta 1 ekle ve departure + 1 noktasında 1 çıkar. En büyük kümülatif toplam yanıttır: O(n + 2400) zaman. 1260 ile 1299 arasındaki indeksler gibi değerler saat değildir ve bunlara varış olmaz; bu nedenle hiçbir zaman zirve oluşturmazlar.

def minimumPlatforms(arrival, departure):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

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

Beklenen Çıktı