Trình lập lịch tác vụ — Leetcode 621

Liên kết vấn đề ban đầu:https://leetcode.com/problems/task-scheduler/description/

Trong bài toán này, chúng ta được yêu cầu tính toán thời gian tối thiểu cần thiết để hoàn thành tất cả các nhiệm vụ (mỗi nhiệm vụ mất 1 đơn vị thời gian) trong một mảng, với thời gian hồi chiêu là n đơn vị giữa các nhiệm vụ giống nhau (có thể được lấp đầy bởi các nhiệm vụ khác nhau). nhiệm vụ).

Chúng ta có thể tìm thấy câu trả lời trực tiếp bằng toán học. Trực giác đằng sau giải pháp của tôi là tìm tần suất tối đa của bất kỳ nhiệm vụ nào và số lượng nhiệm vụ như vậy với tần suất tối đa. Sau đó, chúng tôi phân phối đều phần còn lại của các tác vụ trên mỗi chu kỳ và thêm vào mỗi chu kỳ các đơn vị thời gian nhàn rỗi nếu cần. Mỗi biến có một nhận xét về nó giải thích ý nghĩa của nó.

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