Planificateur de tâches — Leetcode 621

Lien du problème d'origine :https://leetcode.com/problems/task-scheduler/description/

Dans ce problème, on nous demande de calculer le temps minimum nécessaire pour terminer toutes les tâches (qui prennent 1 unité de temps chacune) dans un tableau, étant donné un temps de recharge de n unités entre les mêmes tâches (qui peuvent être remplies par d'autres tâches différentes Tâches).

Nous pouvons trouver la réponse directement en utilisant les mathématiques. L'intuition derrière ma solution est de trouver la fréquence maximale de toutes les tâches et le nombre de ces tâches avec la fréquence maximale. Ensuite, nous distribuons le reste des tâches uniformément sur chaque cycle, et complétons chaque cycle avec des unités de temps d'inactivité si nécessaire. Chaque variable est accompagnée d'un commentaire expliquant sa signification.

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