Task Scheduler

Q: Berapa kompleksitas waktu Task Scheduler?

Menghitung huruf membutuhkan waktu O(m) untuk m tugas, lalu rumusnya membaca 26 hitungan, jadi solusi ini membutuhkan waktu O(m) dan memori tambahan O(1) . Simulasi max-heap melakukan pop sekali untuk setiap tugas, O(m log k) dengan k ≤ 26 huruf.

Q: Kapan Task Scheduler tidak memerlukan waktu idle?

Ketika m ≥ (top-1) × (n+1) + atTop , tugas mengisi setiap slot yang kosong dan meregangkan kerangka alih-alih menyisakan celah, jadi jawabannya adalah m . Contoh 2, "ABCABD" dengan n = 1 , adalah kasus seperti ini.

SedangGreedy Heap Hashing

+10

Kamu mendapatkan string tasks yang terdiri dari huruf kapital, satu huruf untuk setiap tugas, dan sebuah bilangan bulat n. Sebuah prosesor menjalankan satu tugas per satuan waktu, dalam urutan apa pun yang kamu pilih, atau tetap diam selama satu satuan waktu.

Dua kali menjalankan huruf yang sama harus berjarak setidaknya n satuan waktu: huruf yang dijalankan pada satuan waktu t dapat dijalankan lagi paling cepat pada satuan waktu t+n+1. Kembalikan jumlah satuan waktu paling sedikit untuk menjalankan setiap tugas.

Fungsi

leastInterval(tasks: string, n: integer) → integer

tasksstring: tugas-tugas, masing-masing satu huruf kapital
ninteger: jumlah unit paling sedikit di antara dua rangkaian huruf yang sama
Mengembalikaninteger: jumlah unit paling sedikit, termasuk unit yang tidak aktif

Batasan

1 ≤ tasks.length ≤ 10⁴
tasks hanya berisi huruf kapital A sampai Z.
0 ≤ n ≤ 100

Contoh

Input: tasks = "CACBAC"n = 2
Output: 7
Penjelasan: C berjalan tiga kali dengan jeda dua unit di antara setiap kali berjalan, jadi ketiga kalinya berjalan mencakup 7 unit. Urutan C A B C A, jeda, C mengisi celah dengan A dan B, serta membutuhkan satu unit jeda: 7.

Input: tasks = "ABCABD"n = 1
Output: 6
Penjelasan: A dan B masing-masing dijalankan dua kali dengan jeda satu unit di antara setiap kali dijalankan. Urutan A B C A B D memisahkan keduanya tanpa unit menganggur, jadi jawabannya adalah jumlah tugas, 6.

Input: tasks = "ZZZ"n = 3
Output: 9
Penjelasan: Hanya Z yang ada untuk dijalankan, jadi setiap jeda adalah waktu menganggur: Z, tiga unit menganggur, Z, tiga unit menganggur, Z. Totalnya 9 unit.

Pertanyaan lanjutan

Bisakah kamu juga mengembalikan satu jadwal dengan durasi paling singkat, sebagai string dengan . untuk setiap unit waktu kosong?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Kamu yang memilih urutannya, jadi pertanyaannya adalah berapa sedikit unit menganggur yang kamu perlukan. Huruf yang paling sering muncul menentukan jumlahnya: kemunculan huruf itu harus berjarak n+1 unit, dan tugas lainnya mengisi celah di antaranya. Jalankan huruf yang paling sering muncul terlebih dahulu menggunakan max-heap, atau hitung celah secara langsung dengan satu rumus.

Simulasikan ronde dengan max-heap

Intuisi

Bagi waktu menjadi putaran yang masing-masing terdiri dari n+1 unit. Setiap huruf hanya boleh dijalankan satu kali dalam satu putaran, dan huruf pada slot tertentu dalam satu putaran boleh dijalankan lagi pada slot yang sama di putaran berikutnya, tepat n+1 unit kemudian. Di setiap putaran, jalankan huruf yang masih memiliki salinan terbanyak. Jarak antarjalannya harus tetap n+1 unit, jadi huruf-huruf itulah yang dapat memaksa adanya waktu menganggur di akhir. Menjalankannya terlebih dahulu membuat jumlahnya tetap seimbang.

Putaran yang masih menyisakan pekerjaan membutuhkan n+1 unit, dengan slot kosongnya menjadi waktu menganggur; putaran terakhir hanya membutuhkan waktu untuk tugas yang dijalankan. Pada contoh 1, putarannya menjalankan C A B, lalu C A dan satu unit menganggur, kemudian C terakhir: 3 + 3 + 1 = 7. Setiap operasi pop menjalankan satu tugas, jadi dengan m tugas dan k ≤ 26 huruf, kompleksitasnya adalah O(m log k).

Algoritma

Hitung setiap huruf dan masukkan hitungan yang lebih dari nol ke dalam max-heap.
Selama heap tidak kosong, jalankan satu putaran: ambil hingga n+1 hitungan dan simpan setiap hitungan dikurangi satu yang masih lebih dari nol.
Masukkan kembali hitungan yang disimpan.
Tambahkan n+1 ke waktu jika heap tidak kosong. Jika tidak, tambahkan jumlah tugas yang dijalankan pada putaran tersebut.
Kembalikan waktu.

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 time

Hitung jumlah kemunculan huruf yang paling sering muncul

Intuisi

Misalkan top adalah jumlah tertinggi, yang dimiliki huruf X. Susun X dengan n slot kosong setelah setiap rangkaian, kecuali rangkaian terakhir: top-1 kerangka yang masing-masing terdiri dari n+1 unit, lalu rangkaian terakhir X. Huruf yang jumlahnya kurang dari top dapat mengisi slot kosong, satu salinan per kerangka, sehingga jarak antar salinannya setidaknya n+1. Setiap huruf lain yang memiliki top salinan menambahkan satu unit di akhir. Jika ada atTop huruf dengan jumlah tertinggi, totalnya adalah (top-1) × (n+1) + atTop unit.

Tidak ada penjadwalan yang lebih singkat: bagi (top-1) × (n+1) unit pertama menjadi top-1 jendela yang masing-masing terdiri dari n+1. Setiap huruf dengan jumlah tertinggi muncul paling banyak sekali di setiap jendela, sehingga semua atTop huruf itu masih memiliki satu rangkaian tersisa setelah jendela-jendela tersebut. Jika tugas lebih banyak daripada slot kosong, biarkan beberapa kerangka bertambah panjang melebihi n+1. Kerangka yang lebih panjang hanya memperlebar jarak, sehingga tidak ada waktu menganggur dan jawabannya adalah m. Jawabannya adalah nilai yang lebih besar dari keduanya.

Algoritma

Hitung masing-masing dari 26 huruf.
Temukan top, jumlah tertinggi, dan atTop, banyaknya huruf yang memiliki jumlah tersebut.
Hitung frames = (top-1) × (n+1) + atTop.
Kembalikan nilai yang lebih besar antara frames dan jumlah tugas.

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))

Jebakan dan kasus tepi

Melupakan huruf-huruf yang memiliki jumlah tertinggi. Dalam "MMNNPP" dengan n = 5, ketiga huruf masing-masing memiliki jumlah 2, jadi jawabannya adalah (2-1) × 6 + 3 = 9, bukan 7.
Melupakan langkah mengambil nilai yang lebih besar. Dalam contoh 2, kerangka waktunya menghasilkan (2-1) × 2 + 2 = 4, tetapi enam tugas memerlukan enam satuan.
Menghitung putaran terakhir sebagai n+1 satuan penuh. Tidak ada jeda setelah tugas terakhir, jadi contoh 3 akan menghasilkan 12, bukan 9.
Memasukkan kembali jumlah ke dalam putaran yang sama. Huruf yang sama kemudian bisa diambil lagi pada putaran itu dan dijalankan dua kali dengan jeda yang terlalu singkat.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Task Scheduler?

Menghitung huruf membutuhkan waktu O(m) untuk m tugas, lalu rumusnya membaca 26 hitungan, jadi solusi ini membutuhkan waktu O(m) dan memori tambahan O(1). Simulasi max-heap melakukan pop sekali untuk setiap tugas, O(m log k) dengan k ≤ 26 huruf.

Kapan Task Scheduler tidak memerlukan waktu idle?

Ketika m ≥ (top-1) × (n+1) + atTop, tugas mengisi setiap slot yang kosong dan meregangkan kerangka alih-alih menyisakan celah, jadi jawabannya adalah m. Contoh 2, "ABCABD" dengan n = 1, adalah kasus seperti ini.

Apakah urutan string input berpengaruh?

Tidak. Kamu menentukan urutan prosesor menjalankan tugas, jadi yang penting hanya berapa kali setiap huruf muncul. "CACBAC" dan "CCCAAB" dengan n = 2 sama-sama membutuhkan 7 unit.

def leastInterval(tasks, n):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

tasks = "CACBAC"
n = 2

Output yang diharapkan