Task Scheduler
Sana, her görev için bir harf olmak üzere büyük harflerden oluşan bir tasks dizgesi ve bir n tamsayısı veriliyor. Bir işlemci, seçtiğin herhangi bir sırayla zaman birimi başına bir görev çalıştırır veya bir zaman birimi boyunca boşta kalır.
Aynı harfin iki çalıştırılması arasında en az n zaman birimi bulunmalıdır: t zaman biriminde çalışan bir harf, en erken t+n+1 zaman biriminde yeniden çalışabilir. Tüm görevleri çalıştırmak için gereken en az zaman birimi sayısını döndür.
Fonksiyon
- tasksstring
- görevler, her biri bir büyük harf
- ninteger
- aynı harfin iki tekrar dizisi arasındaki en az birim sayısı
- Döndürürinteger
- boştakiler de dâhil olmak üzere en az sayıda birim
Kısıtlar
1 ≤ tasks.length ≤ 104tasksyalnızcaAileZarasındaki büyük harfleri içerir.0 ≤ n ≤ 100
Örnekler
- Girdi
- tasks = "CACBAC"n = 2
- Çıktı
- 7
- Açıklama
- C iki çalışma arasında iki birim olacak şekilde üç kez çalışır; bu nedenle yalnızca C'nin çalışmaları toplam 7 birim sürer.
C A B C A, boşta,Csıralaması boşlukları A ve B ile doldurur ve bir boşta birim gerektirir:7.
- Girdi
- tasks = "ABCABD"n = 1
- Çıktı
- 6
- Açıklama
- A ve B, çalıştırmalarının arasında bir birim olacak şekilde ikişer kez çalıştırılır.
A B C A B Dsırası, aralarında boşta geçen bir birim olmadan onları ayrı tutar; dolayısıyla yanıt görev sayısıdır:6.
- Girdi
- tasks = "ZZZ"n = 3
- Çıktı
- 9
- Açıklama
- Yalnızca Z çalışacak, bu yüzden her boşlukta işlem yapılmayacak: Z, üç boş birim, Z, üç boş birim, Z. Bu,
9birimdir.
Ek soru
Her boşta geçen birim için bir . içeren bir dize olarak, en kısa uzunluğa sahip bir çizelgeyi de döndürebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Hangi harf boşta kalma süresini kaçınılmaz kılar? En sık görünen harfi ve tekrarlarının ne kadar aralıklı olması gerektiğini düşün.
En sık görülen harfi önce yerleştir: bir dizi,
naçık yer, başka bir dizi ve bu şekilde devam et. Bu kaç birim sürer ve açık yerlere ne gelebilir?topen yüksek sayı veatTopbu sayıya sahip harflerin sayısı olduğunda, çerçeveler(top-1) × (n+1) + atTopbirim kaplar. Bunu görev sayısıyla karşılaştırın.
Çözüm
Sıralamayı sen seçersin; dolayısıyla soru, kaç boş birime ihtiyaç duyduğundur. En sık görülen harf belirleyicidir: bu harfin tekrarları arasında n+1 birim bulunmalı ve diğer görevler aradaki boşlukları doldurmalıdır. En sık görülen harfleri önce bir max-heap kullanarak çalıştırabilir ya da boşlukları tek bir formülle doğrudan hesaplayabilirsin.
Bir maksimum yığınla turları simüle edin
Sezgi
Zamanı n+1 birimlik turlara bölün. Bir turda hiçbir harf iki kez çalıştırılamaz; bir turun herhangi bir zaman diliminde çalıştırılan bir harf, sonraki turda tam n+1 birim sonra aynı zaman diliminde yeniden çalıştırılabilir. Her turda, en çok kopyası kalan harfleri çalıştırın. Bu harflerin kalan çalıştırmaları arasında n+1 birim bulunmalıdır; bu nedenle turun sonunda boşta kalma süresini zorunlu kılabilecek harfler onlardır. Önce bunları çalıştırmak, sayıları dengede tutar.
Geride iş bırakan bir tur n+1 birime mal olur; boş kalan zaman dilimleri boşta geçer. Son tur ise yalnızca çalıştırdığı görevler kadar sürer. Örnek 1'de turlar önce C A B'yi, sonra C A'yı ve bir boşta birimi, ardından son C'yi çalıştırır: 3 + 3 + 1 = 7. Her çıkarma bir görevi çalıştırdığından, m görev ve k ≤ 26 harfle bu işlem O(m log k) olur.
Algoritma
- Her harfi say ve sıfırdan büyük sayımları bir maksimum yığına koy.
- Yığın boş değilken bir tur çalıştır: en fazla
n+1sayım çıkar ve hâlâ sıfırdan büyük olan her sayımdan bir çıkarıp onları tut. - Tutulan sayımları tekrar yığına ekle.
- Yığın boş değilse süreye
n+1ekle; değilse turun çalıştırdığı görev sayısını ekle. - Süreyi döndür.
import heapq
from collections import Counter
def leastInterval(tasks, n):
# heapq is a min-heap, so store negated counts to pop the largest first.
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap)
time = 0
while heap:
# One round of n+1 slots: run the most frequent tasks left, each at most once.
left = []
ran = 0
while ran < n + 1 and heap:
c = -heapq.heappop(heap)
ran += 1
if c > 1:
left.append(c - 1)
for c in left:
heapq.heappush(heap, -c)
# A round lasts n+1 units, idle included; the last one ends with its last task.
time += n + 1 if heap else ran
return timeEn sık kullanılan harfin karelerini say
Sezgi
top, X harfinin sahip olduğu en yüksek sayı olsun. Son çalıştırma hariç, her çalıştırmadan sonra n boş yuva bırakarak X'i yerleştir: n+1 birimlik top-1 çerçeve, ardından X'in son çalıştırması. top sayısından daha az kopyası olan bir harf boş yuvalara, her çerçeveye bir kopya gelecek şekilde sığar; böylece kopyaları arasında en az n+1 birim kalır. top kopyası olan diğer her harf sona bir birim ekler. En yüksek sayıya sahip atTop harf olduğunda, bu (top-1) × (n+1) + atTop birim eder.
Hiçbir çizelge daha kısa olamaz: İlk (top-1) × (n+1) birimi n+1 birimlik top-1 pencereye böl. Her en yüksek sayıya sahip harf her pencerede en fazla bir kez çalıştırılabilir; dolayısıyla pencerelerden sonra bu atTop harfin tümünün hâlâ bir çalıştırması kalır. Açık yuvalardan daha fazla görev varsa bazı çerçevelerin n+1 birimden uzun olmasına izin ver. Daha uzun bir çerçeve aralıkları yalnızca genişletir; böylece hiçbir şey boşta kalmaz ve yanıt m olur. Yanıt, bu iki değerden büyük olanıdır.
Algoritma
- 26 harfin her birini say.
- En yüksek sayı olan
top'u ve bu sayıya sahip kaç harf olduğunu belirtenatTop'u bul. frames = (top-1) × (n+1) + atTopdeğerini hesapla.framesile görev sayısından büyük olanı döndür.
def leastInterval(tasks, n):
counts = [0] * 26
for ch in tasks:
counts[ord(ch) - ord("A")] += 1
top = max(counts)
at_top = counts.count(top) # tasks that share the highest count
# top-1 full frames of n+1 units, then one last slot per task at the top count.
frames = (top - 1) * (n + 1) + at_top
# With more tasks than frame slots, no idle unit is needed at all.
return max(frames, len(tasks))
Tuzaklar ve uç durumlar
- En üstte berabere kalan harfleri unutmak.
"MMNNPP"dizisinden = 5iken üç harfin de sayısı 2'dir; bu nedenle cevap 7 değil,(2-1) × 6 + 3 = 9olur. - En büyük olanı alma adımını unutmak. Örnek 2'de çerçeveler
(2-1) × 2 + 2 = 4verir, ancak altı görev altı birim gerektirir. - Son tura tam
n+1birim eklemek. Son görevden sonra bekleme olmaz: örnek 3'ün sonucu 9 yerine 12 olur. - Bir sayımı tur bitmeden geri eklemek. Böylece aynı harf aynı turda yeniden çıkarılabilir ve aralarında yeterli süre olmadan iki kez çalıştırılabilir.
Sıkça sorulan sorular3
Task Scheduler'ın zaman karmaşıklığı nedir?
Harfleri saymak m görev için O(m) sürer ve formül daha sonra 26 sayımı okur; dolayısıyla çözüm O(m) zaman ve O(1) ek bellek gerektirir. Maksimum yığın benzetimi her görev için bir kez çıkarma yapar; k ≤ 26 harf için karmaşıklığı O(m log k) olur.
Görev Zamanlayıcısı ne zaman boşta kalma süresine ihtiyaç duymaz?
m ≥ (top-1) × (n+1) + atTop olduğunda, görevler tüm açık yuvaları doldurur ve boşluk bırakmak yerine çerçeveleri genişletir; bu nedenle yanıt m olur. Örnek 2'deki "ABCABD" ve n = 1 böyle bir durumdur.
Girdi dizgesinin sırası önemli mi?
Hayır. İşlemcinin görevleri hangi sırayla çalıştıracağını sen seçersin; bu yüzden yalnızca her harfin kaç kez geçtiği önemlidir. "CACBAC" ve "CCCAAB", n = 2 için ikisi de 7 birim gerektirir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
def leastInterval(tasks, n):
# Kodu buraya yazınTest #1
Test #2
Test #3
Argümanlar
tasks = "CACBAC" n = 2
Beklenen Çıktı
7