Aralık temelleri ve sıralama
Adım 1/8
Dört toplantı, rezerve edildikleri sırayla çizildi. Her biri yalnızca bir başlangıç ve bitiş.
Fikir
Aralık sadece bir çifttir: başlangıç ve bitiş. İki aralık, her biri diğeri bitmeden başlıyorsa çakışır — tek bir test, hiç özel durum yok.
Her çifti kontrol etmek n kare tutar. Başlangıca göre sıralamak n log n tutar ve ardından işe yarar bir şeyi garanti eder: karşına çıkan her aralık, elinde tuttuğunla aynı anda ya da ondan sonra başlar.
Gerçek hayattan örnek
Günü soldan sağa çizen ortak bir takvim düşün. Kimse salının dördüncü toplantısını ilkiyle karşılaştırmaz — çakışmalar görünür, çünkü çubuklar zaman sırasına göre dizilmiştir; başlangıca göre sıralamanın yaptığı da tam olarak bu.
Kod
Sıra sende
Bu kod ne yazdırır?
spans = [(5, 8), (1, 4), (1, 2)]
spans.sort()
print(spans[0])Mini quiz
1 / 3