Aralıkları Başlangıca Göre Sıralama

Bir aralık, [2, 5] gibi başlangıç ve bitişten oluşan bir sayı çiftidir. Aralık problemlerinin çoğu bu çiftlerin bir listesinden oluşur. 📏

Ham aralıklar herhangi bir sırada gelebilir ve bu da onlar hakkında akıl yürütmeyi zorlaştırır. Önce sıralamak, karmaşayı temiz bir soldan sağa taramaya dönüştürür.

Varsayılan işlem, başlangıç değerine göre sort kullanmaktır. Artık her aralık kendisinden öncekinin başladığı konumda veya daha sonra başlar; böylece bir kez ileri doğru tarayabilirsiniz.

Aralıkları demet olarak saklarsanız Python bunları ücretsiz olarak önce ilk elemana, sonra ikinci elemana göre sıralar. Burada bir anahtar işlevine bile gerek yoktur.

Başlangıca göre sıralamak, olayları zaman sırasıyla işlemenizi sağlar. Bir sonraki aralık ancak daha sonra başlayabilir; tarama için temel değişmez budur.

İki aralığın başlangıcı aynı olduğunda sıralamayı ikincil anahtar belirler. (başlangıç, bitiş) biçiminde sıralamak, daha kısa aralıkları önce tutar ve bu çoğu zaman işe yarar.

En fazla olayı planlamak gibi bazı problemlerde bunun yerine bitişe göre sıralama yapılır. Taramanızın bilmesi gerekenlere uyan anahtarı seçin.

Sıralama O(n log n) zaman alır; bu maliyet düşüktür ve genellikle bu problemlerde baskın olan kısımdır. Ardından gelen tarama yalnızca O(n) sürer.

Her aralık bir kimlik veya ağırlık taşıyorsa yalnızca sınırları değil, tüm kaydı sıralayın. Anahtar sırayı belirlerken veriler de onunla birlikte hareket eder.

Neredeyse her aralık algoritması önce sort kullanın, sonra tarayın ilkesine dayanır. Sırayı doğru kurduğunuzda birleştirme, sayma ve planlama basit döngülere dönüşür.

Aralıkları bir partiye gelen konuklar olarak düşünün. Başlangıca göre sıralamak, onları geliş zamanlarına göre sıraya dizer ve tek tek karşılamanızı sağlar.

Bir aralık listesini birleştirmek üzeresiniz.

Aralık, başlangıç-bitiş çiftidir; başlangıca göre sıralamak dağınık listeyi temiz bir taramaya dönüştürür. Önce sıralayın, ardından O(n) sürede ileri doğru işleyin. 🚀