İçeriğe geç

Aralık temelleri ve sıralama

Ders 1 / 4 · 4 dk

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

İki aralık, a ve b, ne zaman çakışır?