Her toplantıya katıl
Görev tanımı
Problem
Bir takvim toplantıları belirli bir sırası olmayan [start, end] çiftleri olarak listeliyor. Bir kişinin her toplantıya baştan sona katılıp katılamayacağına karar ver. Biri tam diğeri başlarken biten toplantılar sorun değil, çünkü kişi birinden diğerine doğrudan geçebilir.
Örnekler
Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: False
Neden: uzun toplantı diğer ikisini de yutuyor
Input: meetings = [[7, 10], [2, 4], [4, 7]]
Output: True
Neden: zaman sırasında toplantılar yalnız uçlarında değiyor
Input: meetings = []
Output: True
Neden: edge case: boş bir takvimde çakışacak bir şey yok
İpuçları
0 / 3
Her toplantı çiftini karşılaştırmak işe yarar ama karesel. Mantıklı bir sırayla bakınca hangi çiftlerin gerçekten çakışabileceğini düşün.
Başlangıç zamanına göre sıraladıktan sonra bir toplantı yalnız kendisinden önce başlayan bir şeyle çakışabilir; hâlâ sürüyor olma ihtimali en yüksek olan da hemen önündekidir.
Başlangıç zamanına göre sırala ve listeyi bir kez dolaş. Bir toplantı önceki toplantı bitmeden başlıyorsa False döndür. Dolaşma biterse True döndür.
- Hedef zaman
- O(n log n)
- Hedef alan
- O(n)
Çözüm
Toplantılar başlangıç zamanına göre sıralanınca ikisinin örtüşebilmesinin tek yolu bir toplantının hemen öncülü bitmeden başlamasıdır: bu sırada komşular hiç örtüşmüyorsa bitiş zamanları da sıralıdır, yani daha gerideki hiçbir şey onların ötesine uzanamaz. Bu, ikili bir soruyu bitişik çift başına bir karşılaştırmaya çevirir; değen toplantılar geçsin diye kesin küçüktür karşılaştırmasıyla. Sıralama için zaman O(n log n), sıralı kopya için alan O(n).
def can_attend_all(meetings):
ordered = sorted(meetings) # by start time
for prev, cur in zip(ordered, ordered[1:]):
if cur[0] < prev[1]: # starts before the last one ends
return False
return True
print(can_attend_all([[0, 30], [5, 10], [15, 20]])) # -> False
print(can_attend_all([[7, 10], [2, 4], [4, 7]])) # -> True
print(can_attend_all([])) # -> TrueKodda değil de fikirde mi takıldın? Meeting Rooms bunu anlatıyor.