Penjadwal Tugas — Leetcode 621

Tautan masalah asli:https://leetcode.com/problems/task-scheduler/description/

Dalam soal ini, kita diminta untuk menghitung waktu minimum yang diperlukan untuk menyelesaikan semua tugas (yang masing-masing membutuhkan 1 unit waktu) dalam sebuah array, dengan waktu cooldown n unit antara tugas yang sama (yang dapat diisi oleh tugas lain yang berbeda). tugas).

Kita dapat menemukan jawabannya secara langsung menggunakan matematika. Intuisi di balik solusi saya adalah menemukan frekuensi maksimum dari setiap tugas dan jumlah tugas tersebut dengan frekuensi maksimum. Kemudian kami mendistribusikan sisa tugas secara merata pada setiap siklus, dan mengisi setiap siklus dengan unit waktu idle jika perlu. Setiap variabel memiliki komentar yang menjelaskan maknanya.

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;
    }
}