説明

文字配列 tasks が与えられた場合、CPU が実行する必要があるタスクを表し、各文字は異なるタスクを表します.タスクは任意の順序で実行できます.各タスクは 1 単位時間で実行されます.単位時間ごとに、CPU は 1 つのタスクを完了するか、単にアイドル状態になる可能性があります.

ただし、2 つの同じタスク間のクールダウン期間を表す非負の整数 n があります(配列内の同じ文字).つまり、2 つの同じタスク間に少なくとも n 単位の時間がある必要があります.

CPU が指定されたすべてのタスクを完了するのにかかる最小単位数を返します.

💡注:

例 1:

Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: 
A -> B -> idle -> A -> B -> idle -> A -> B
There is at least 2 units of time between any two same tasks.

例 2:

Input: tasks = ["A","A","A","B","B","B"], n = 0
Output: 6
Explanation: On this case any permutation of size 6 would work since n = 0.
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
And so on.

例 3:

Input: tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
Output: 16
Explanation: 
One possible solution is
A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> idle -> idle -> A -> idle -> idle -> A

制約:

1 <= task.length <= 104

tasks[i] は大文字の英字です.

整数 n は [0, 100] の範囲にあります.

ソリューション

解決策 1

直感

コード

public int leastInterval(char[] tasks, int n) {
    int[] frequencies = new int[26];
    int max = Integer.MIN_VALUE;
    for (int task : tasks) {
        frequencies[task - 'A']++;
        max = Math.max(max, frequencies[task - 'A']);
    }
    int maxCount = 0;
    for (int frequency : frequencies) {
        if (frequency == max) {
            maxCount++;
        }
    }
    return Math.max(tasks.length, (max - 1) * (n + 1) + maxCount);
}

複雑

時間: O(n)

スペース: O(1)

解決策 2

直感

タスクの頻度を作成します.

大きなものから小さなものへとヒープを構築する必要があります

スロットで各タスクを処理する

最後のスロットを覚えておいてください.ヒープが空かどうかを確認し、スロット全体ではなく作業時間を追加する必要があります

コード

public int leastInterval(char[] tasks, int n) {
    HashMap<Character, Integer> frequencies = new HashMap<>();
    for (char task : tasks) {
        frequencies.put(task, frequencies.getOrDefault(task, 0) + 1);
    }
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
    heap.addAll(frequencies.values());

    int slot = n + 1, time = 0;
    while (!heap.isEmpty()) {
        int workingTime = 0;
        ArrayList<Integer> unfinishedTasks = new ArrayList<>();
        for (int i = 0; i < slot; i++) {
            if (!heap.isEmpty()) {
                                // process task: task - 1
                unfinishedTasks.add(heap.poll() - 1);
                workingTime++;
            }
        }
        for (Integer unfinishedTask : unfinishedTasks) {
            if (unfinishedTask > 0) {
                heap.add(unfinishedTask);
            }
        }
        time += heap.isEmpty() ? workingTime : slot;
    }
    return time;
}

複雑

時間: O(n)

スペース: O(1)