タスク スケジューラ — Leetcode 621

元の問題リンク:https://leetcode.com/problems/task-scheduler/description/

この問題では、配列内のすべてのタスク (それぞれ 1 単位時間かかる) を完了するのに必要な最小時間を計算するように求められます。タスク)。

数学を使って直接答えを見つけることができます。私のソリューションの背後にある直感は、タスクの最大頻度と、最大頻度を持つそのようなタスクの数を見つけることです。次に、残りのタスクを各サイクルに均等に分散し、必要に応じて各サイクルにアイドル時間ユニットを埋め込みます。各変数には、その意味を説明するコメントがあります。

class Solution {

    public int leastInterval(char[] tasks, int n) {
        if (n == 0) {
            return tasks.length;
        }
        Map<Character, Integer> taskMap = new HashMap<>();
        // highest frequency of the same task appearing
        int maxFrequency = 0;
        for (char task : tasks) {
            taskMap.put(task, taskMap.getOrDefault(task, 0) + 1);
            maxFrequency = Math.max(taskMap.get(task), maxFrequency);
        }

        // number of such max frequency tasks
        int maxFreqTasks = 0;
        for (char task : taskMap.keySet()) {
            if (taskMap.get(task) == maxFrequency) {
                maxFreqTasks++;
            }
        }

        // rest of the tasks
        int nonMaxFreqTasks = tasks.length - (maxFreqTasks * maxFrequency);
        // rest of the distributed tasks on each cycle
        int cycleLength = maxFrequency > 1 ? (nonMaxFreqTasks / (maxFrequency - 1)) : 0;
        // extra tasks distributed to the first few cycles if any
        int remaining = maxFrequency > 1 ? (nonMaxFreqTasks % (maxFrequency - 1)) : 0;

        // total length of each cycle (minus remaining)
        int cycle = maxFreqTasks + cycleLength;
        int idle = 0;
        // distribute idles if needed
        if (cycle + 1 <= n && remaining > 0) {
            idle += ((maxFrequency - 1) * (n - cycle));
        } else if (cycle <= n && remaining == 0) {
            idle += ((maxFrequency - 1) * (n - cycle + 1));
        }
        // add extra idles for the cycles that didn't get the "remaining" tasks
        if (remaining > 0 && cycle <= n) {
            idle += (maxFrequency - 1 - remaining);
        }
        return tasks.length + idle;
    }
}