Task Scheduler

Q: Độ phức tạp thời gian của Task Scheduler là gì?

Việc đếm các chữ cái mất O(m) với m tác vụ, sau đó công thức đọc 26 số đếm, nên lời giải có thời gian O(m) và dùng thêm bộ nhớ O(1) . Mô phỏng hàng đợi ưu tiên tối đa lấy ra một lần cho mỗi tác vụ, có độ phức tạp O(m log k) với k ≤ 26 chữ cái.

Q: Khi nào Task Scheduler không cần thời gian nhàn rỗi?

Khi m ≥ (top-1) × (n+1) + atTop , các tác vụ lấp đầy mọi chỗ trống và kéo dài các khung thay vì để lại khoảng trống, vì vậy đáp án là m . Ví dụ 2, "ABCABD" với n = 1 , thuộc trường hợp này.

Trung bìnhTham lam Heap Băm

+10

Bạn có một chuỗi tasks gồm các chữ cái viết hoa, mỗi chữ cái tương ứng với một tác vụ, và một số nguyên n. Bộ xử lý chạy một tác vụ trong mỗi đơn vị thời gian theo thứ tự bạn chọn, hoặc nghỉ một đơn vị.

Hai lần chạy cùng một chữ cái phải cách nhau ít nhất n đơn vị: nếu một chữ cái chạy ở đơn vị t, sớm nhất chữ đó có thể chạy lại là ở đơn vị t+n+1. Hãy trả về số đơn vị thời gian ít nhất để chạy mọi tác vụ.

Hàm

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

tasksstring: các nhiệm vụ, mỗi nhiệm vụ là một chữ cái viết hoa
ninteger: số đơn vị ít nhất nằm giữa hai lần xuất hiện của cùng một chữ cái
Trả vềinteger: số lượng đơn vị ít nhất, bao gồm cả những đơn vị không hoạt động

Ràng buộc

1 ≤ tasks.length ≤ 10⁴
tasks chỉ chứa các chữ cái in hoa từ A đến Z.
0 ≤ n ≤ 100

Ví dụ

Đầu vào: tasks = "CACBAC"n = 2
Đầu ra: 7
Giải thích: C chạy ba lần, với hai đơn vị giữa các lần chạy, nên riêng các lần chạy của C kéo dài 7 đơn vị. Thứ tự C A B C A, nghỉ, C lấp đầy các khoảng trống bằng A và B, đồng thời cần một đơn vị nghỉ: 7.

Đầu vào: tasks = "ABCABD"n = 1
Đầu ra: 6
Giải thích: A và B mỗi tác vụ chạy hai lần, với một đơn vị thời gian giữa các lần chạy. Thứ tự A B C A B D giữ khoảng cách giữa chúng mà không có đơn vị thời gian nào nhàn rỗi, nên đáp án là số tác vụ, 6.

Đầu vào: tasks = "ZZZ"n = 3
Đầu ra: 9
Giải thích: Chỉ có Z để chạy, nên mọi khoảng trống đều nhàn rỗi: Z, ba đơn vị nhàn rỗi, Z, ba đơn vị nhàn rỗi, Z. Tổng cộng là 9 đơn vị.

Câu hỏi mở rộng

Bạn cũng có thể trả về một lịch trình có độ dài ngắn nhất, dưới dạng chuỗi với một dấu . cho mỗi đơn vị thời gian nhàn rỗi không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Bạn chọn thứ tự, vậy câu hỏi là cần ít đơn vị nhàn rỗi nhất là bao nhiêu. Chữ cái xuất hiện nhiều nhất sẽ quyết định: các lần xuất hiện của chữ đó phải cách nhau n+1 đơn vị, còn các tác vụ khác lấp đầy khoảng trống ở giữa. Hãy chạy các chữ cái xuất hiện nhiều nhất trước bằng đống cực đại (max-heap), hoặc tính trực tiếp các khoảng trống bằng một công thức.

Mô phỏng các lượt bằng đống cực đại

Ý tưởng

Chia thời gian thành các vòng gồm n+1 đơn vị. Không chữ cái nào được chạy hai lần trong một vòng, và một chữ cái ở một vị trí nào đó trong một vòng có thể chạy lại ở cùng vị trí trong vòng tiếp theo, đúng n+1 đơn vị sau. Trong mỗi vòng, chạy các chữ cái còn nhiều bản sao nhất. Các lần chạy còn lại của chúng phải cách nhau n+1 đơn vị, vì vậy chúng có thể buộc phải có thời gian nhàn rỗi ở cuối; chạy chúng trước giúp số lượng được cân bằng.

Một vòng còn việc cần làm sẽ tốn n+1 đơn vị, các vị trí trống trong vòng đó là thời gian nhàn rỗi; vòng cuối chỉ tốn số đơn vị dành cho các tác vụ được chạy. Trong ví dụ 1, các vòng lần lượt chạy C A B, rồi C A và một đơn vị nhàn rỗi, sau đó là C cuối cùng: 3 + 3 + 1 = 7. Mỗi lần lấy ra sẽ chạy một tác vụ, nên với m tác vụ và k ≤ 26 chữ cái, độ phức tạp là O(m log k).

Thuật toán

Đếm số lần xuất hiện của từng chữ cái rồi đưa các số đếm lớn hơn 0 vào một đống tối đa.
Khi đống chưa rỗng, thực hiện một vòng: lấy ra tối đa n+1 số đếm và giữ lại mỗi số đếm sau khi giảm đi một, nếu kết quả vẫn lớn hơn 0.
Đưa các số đếm được giữ lại trở về đống.
Cộng n+1 vào thời gian nếu đống chưa rỗng; nếu không, cộng số tác vụ đã chạy trong vòng đó.
Trả về thời gian.

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

Đếm số khung hình của chữ cái xuất hiện thường xuyên nhất

Ý tưởng

Gọi top là số lần xuất hiện nhiều nhất, thuộc về chữ X. Sắp xếp các chữ X sao cho sau mỗi chuỗi, trừ chuỗi cuối cùng, có n vị trí trống: top-1 khung, mỗi khung dài n+1 đơn vị, rồi đến chuỗi X cuối cùng. Một chữ xuất hiện ít hơn top lần có thể được đặt vào các vị trí trống, mỗi khung một lần, nên các lần xuất hiện của chữ đó cách nhau ít nhất n+1 đơn vị. Mỗi chữ khác xuất hiện top lần sẽ thêm một đơn vị ở cuối. Với atTop chữ có số lần xuất hiện nhiều nhất, tổng cộng là (top-1) × (n+1) + atTop đơn vị.

Không có lịch trình nào ngắn hơn: chia (top-1) × (n+1) đơn vị đầu tiên thành top-1 khung, mỗi khung dài n+1. Mỗi chữ xuất hiện nhiều nhất chỉ xuất hiện một lần trong mỗi khung, vì vậy sau các khung đó, cả atTop chữ vẫn còn một lần xuất hiện. Khi có nhiều tác vụ hơn số vị trí trống, hãy để một số khung dài hơn n+1. Khung dài hơn chỉ nới rộng khoảng cách, nên không có thời gian nào bị bỏ trống và đáp án là m. Đáp án là giá trị lớn hơn trong hai giá trị.

Thuật toán

Đếm số lần xuất hiện của từng chữ cái trong 26 chữ cái.
Tìm top, số lần xuất hiện cao nhất, và atTop, số chữ cái có số lần xuất hiện đó.
Tính frames = (top-1) × (n+1) + atTop.
Trả về giá trị lớn hơn giữa frames và số lượng tác vụ.

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

Lỗi thường gặp và trường hợp biên

Quên các chữ cái đồng hạng ở vị trí cao nhất. Trong "MMNNPP" với n = 5, cả ba chữ cái đều có số lần xuất hiện là 2, nên đáp án là (2-1) × 6 + 3 = 9, không phải 7.
Quên bước lấy giá trị lớn hơn. Trong ví dụ 2, các khung cho kết quả (2-1) × 2 + 2 = 4, nhưng sáu tác vụ cần sáu đơn vị.
Tính thêm đủ n+1 đơn vị cho vòng cuối. Không có thời gian chờ sau tác vụ cuối cùng: ví dụ 3 sẽ cho kết quả 12 thay vì 9.
Đưa một số đếm trở lại vòng lặp hiện tại. Khi đó, cùng một chữ cái có thể bị lấy ra lần nữa trong vòng đó và chạy hai lần quá sát nhau.

Câu hỏi thường gặp3

Độ phức tạp thời gian của Task Scheduler là gì?

Việc đếm các chữ cái mất O(m) với m tác vụ, sau đó công thức đọc 26 số đếm, nên lời giải có thời gian O(m) và dùng thêm bộ nhớ O(1). Mô phỏng hàng đợi ưu tiên tối đa lấy ra một lần cho mỗi tác vụ, có độ phức tạp O(m log k) với k ≤ 26 chữ cái.

Khi nào Task Scheduler không cần thời gian nhàn rỗi?

Khi m ≥ (top-1) × (n+1) + atTop, các tác vụ lấp đầy mọi chỗ trống và kéo dài các khung thay vì để lại khoảng trống, vì vậy đáp án là m. Ví dụ 2, "ABCABD" với n = 1, thuộc trường hợp này.

Thứ tự của chuỗi đầu vào có quan trọng không?

Không. Bạn chọn thứ tự bộ xử lý chạy các tác vụ, nên chỉ số lần xuất hiện của mỗi chữ cái mới quan trọng. "CACBAC" và "CCCAAB" với n = 2 đều cần 7 đơn vị.

def leastInterval(tasks, n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

tasks = "CACBAC"
n = 2

Đầu ra mong đợi