Meeting Rooms
Toplantıların listesini iki dizi olarak alırsınız: i numaralı toplantı starts[i] anında başlar ve ends[i] anında biter. Bir kişi bunların hepsine katılmak istiyor, bu nedenle hiçbir iki toplantı çakışmamalıdır. Bir toplantı, başka bir toplantının bittiği anda başlayabilir. Kişi her toplantıya katılabiliyorsa true, aksi takdirde false döndürün.
Fonksiyon
- startsinteger-array
- her toplantının başlangıç saati
- endsinteger-array
- her toplantının bitiş zamanı, başlangıç zamanıyla aynı indekste
- Döndürürboolean
- Hiçbir toplantı çakışmıyorsa true, aksi takdirde false
Kısıtlar
1 ≤ starts.length == ends.length ≤ 50000 ≤ starts[i] < ends[i] ≤ 106- Toplantılar sıralanmamıştır. İki toplantı aynı olabilir.
Örnekler
- Girdi
- starts = [9, 13, 10]ends = [10, 15, 12]
- Çıktı
- true
- Açıklama
- Zaman sırasına göre toplantılar 9'dan 10'a, 10'dan 12'ye ve 13'ten 15'e kadar sürer. İkincisi, ilki biter bitmez başlar; buna izin verildiği için yanıt
trueolur.
- Girdi
- starts = [1, 4, 7]ends = [5, 6, 8]
- Çıktı
- false
- Açıklama
- 1'den 5'e kadar olan toplantı, 4'te 4'ten 6'ya kadar olan toplantı başladığında hâlâ devam ediyor; bu nedenle yanıt
false.
Gönderirken +15 gizli test
Ek soru
Toplantılar her seferinde bir tane rezerve ediliyorsa, her yeni rezervasyonu her şeyi yeniden sıralamadan O(log n) sürede programa göre nasıl kontrol edersiniz?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Çakışan iki toplantının ortak bir zaman aralığı olmalıdır. Komşu toplantılar arasında çakışma görünecek şekilde toplantıları hangi sırayla listeleyebilirsin?
Toplantıları başlangıç saatlerine göre sıralayın. Böylece bir toplantı yalnızca hemen öncesindeki toplantıyla çakışabilir: O toplantı bittikten sonra başlıyorsa, kendisinden önceki tüm toplantılar da bitmiş demektir.
Başlangıçları, her başlangıcı kendi bitişiyle eşleştirerek sırala. Sıralanmış listede ilerle ve her başlangıcı kendisinden önceki toplantının bitişiyle karşılaştır. Daha küçük bir başlangıç çakışma anlamına gelir; bu bitişe eşit bir başlangıç sorun oluşturmaz.
Çözüm
Her toplantı çiftini kontrol etmek çakışmaları bulur, ancak maliyeti O(n²) olur. Başlangıç saatine göre sıralamak soruyu değiştirir: toplantılar sıralı düzende yalnızca yanındaki toplantıyla çakışabilir, bu nedenle toplantı başına bir karşılaştırma yeterlidir.
Her çifti karşılaştır
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Her biri diğeri bitmeden başladığında iki toplantı çakışır. 1'den 5'e ve 4'ten 6'ya kadar süren toplantılar için: 1, 6'dan önce ve 4, 5'ten önce olduğundan çakışırlar. 9'dan 10'a ve 10'dan 12'ye kadar süren toplantılar içinse: 10, 10'dan önce değildir; dolayısıyla bu toplantılar yalnızca uç uca gelir.
Her iki tarafta da katı < kullanmak, bir toplantının tam olarak başka bir toplantı biterken başlamasını sağlar. Her çift üzerinde testi çalıştır ve ilk çakışmada false döndür.
Sorun, çiftlerin sayısıdır. n = 5000 toplantı olduğunda yaklaşık 12,5 milyon çift vardır ve hiç çakışma olmayan bir program, tüm çiftleri kontrol etmek zorunda kalır; bu da en büyük testler için çok yavaştır.
Algoritma
- Her
iindisi ve ondan sonraki herjindisi için: starts[i] < ends[j]vestarts[j] < ends[i]ise iki toplantı çakışır:falsedöndür.- Hiçbir çift çakışmıyorsa
truedöndür.
def canAttendMeetings(starts, ends):
n = len(starts)
for i in range(n):
for j in range(i + 1, n):
# two meetings clash when each one starts before the other ends
if starts[i] < ends[j] and starts[j] < ends[i]:
return False
return TrueBaşlangıç değerine göre sırala ve komşuları kontrol et
Sezgi
Toplantıları başlangıç saatine göre sıralayın ve her başlangıcı kendi bitişiyle eşleştirin. Şimdi herhangi bir toplantıya ve hemen öncesindeki toplantıya bakın. Önceki toplantı, sonraki toplantı başlamadan sonra bitiyorsa çakışırlar. Çakışmıyorsa sonraki toplantı, önceki toplantının bittiği anda veya daha sonra başlar.
Neden kontrol etmeniz gereken tek toplantı komşusudur? Şimdiye kadarki her toplantı, kendisinden öncekinin bitişinde veya daha sonra başlıyorsa şimdiye kadarki toplantılar hiç çakışmaz ve hemen önceki toplantı en geç bitendir. Bitişinde veya daha sonra başlayan yeni bir toplantı, hepsinin bitişinde veya daha sonra başlar.
İlk örnekte sıralanmış toplantılar 9'dan 10'a, 10'dan 12'ye, 13'ten 15'e şeklindedir. 10 başlangıcı, 10 bitişinden önce değildir ve 13 başlangıcı, 12 bitişinden önce değildir; dolayısıyla çakışma yoktur. Eşit başlangıç saatleri her zaman çakışır; çünkü her toplantı en az bir birim sürer ve bu kontrol onları da yakalar.
Sıralama O(n log n) maliyetindedir ve tarama O(n) sürer. Toplantıların eşleştirilmiş kopyası O(n) alan kaplar.
Algoritma
- Her başlangıcı kendi bitişiyle eşleştir.
- Çiftleri başlangıç zamanına göre sırala.
- İlkinden sonraki her toplantı için başlangıç zamanını önceki toplantının bitişiyle karşılaştır.
- Başlangıç daha küçükse
falsedöndür. - Döngüden sonra
truedöndür.
def canAttendMeetings(starts, ends):
meetings = sorted(zip(starts, ends)) # by start time
for i in range(1, len(meetings)):
# a meeting must not start before the one right before it ends
if meetings[i][0] < meetings[i - 1][1]:
return False
return True
Tuzaklar ve uç durumlar
Yaygın hatalar, hangi uçların karşılaştırıldığı ve birbirine değen toplantıların nasıl ele alındığıyla ilgilidir.
startsöğelerini sıralayıpendsöğelerini giriş sırasına göre bırakmak. Her bitiş, kendi başlangıcıyla birlikte hareket etmelidir; yoksa bir başlangıcı başka bir toplantının bitişiyle karşılaştırırsınız.<yerine≤kullanmak. 9'dan 10'a ve 10'dan 12'ye kadar süren toplantılar birbirine değse de çakışmaz ve bu toplantılar için yanıttrueolur.- Yalnızca giriş sırasındaki her toplantının bir sonrakisi başlamadan önce bittiğini kontrol etmek. Girdi sıralı değildir, dolayısıyla girdide yan yana olan toplantılar hiçbir şey göstermez.
- Çift testini
starts[j] < ends[i]gibi tek bir koşulla yazmak. Bu yalnızcajtoplantısı daha geç başladığında işe yarar; bu sırayla 5'ten 6'ya ve 0'dan 1'e kadar süren toplantılar için0 < 6gerçekte olmayan bir çakışma bildirir.
Sıkça sorulan sorular4
Meeting Rooms'un zaman karmaşıklığı nedir?
Toplantıları başlangıç saatine göre sıralamak O(n log n) maliyetlidir ve komşuları karşılaştıran tarama O(n) sürer; dolayısıyla toplam maliyet O(n log n) olur. Bunun yerine her çifti karşılaştırmak O(n²) maliyetlidir.
Neden her toplantıyı bir öncekiyle karşılaştırmak yeterlidir?
Başlangıca göre sıraladıktan sonra, şimdiye kadar herhangi bir çakışma bulunmadıysa, toplantılar birbirini izleyen bir zincir oluşturur; her biri bir öncekinin bitişinde veya sonrasında başlar. Zincirin son toplantısı en geç biter. Bitişinde veya sonrasında başlayan yeni bir toplantı, önceki toplantılardan hiçbiriyle çakışamaz.
Birbirine değen toplantılar çakışıyor sayılır mı?
Bu problemde böyle değil: bir toplantı, başka bir toplantının tam bittiği anda başlayabilir. Bu nedenle kontrol, katı bir start < previous end koşuludur. Birbirine değen toplantılar yasak olsaydı kontrol start ≤ previous end olurdu.
Toplantı odalarının minimum sayısını nasıl bulursunuz?
Başlangıç saatlerini ve bitiş saatlerini iki ayrı liste olarak sıralayın, ardından ikisini de tarayın: her başlangıç bir oda açar ve bir sonraki başlangıçtan önce veya ona eşit zamanda gelen her bitiş bir odayı boşaltır. Aynı anda açık olan oda sayısının en büyük değeri yanıttır. Buradaki evet veya hayır sorusunu yanıtlamak, tek bir odanın yeterli olup olmadığını sormakla aynıdır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def canAttendMeetings(starts, ends):
# Kodu buraya yazınDurum 1
Durum 2
Girdi
starts = [9, 13, 10] ends = [10, 15, 12]
Beklenen
true