[LeetCode]621. Task Scheduler

Description:

Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks.Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.

However, there is a non-negative cooling interval n that means between two same tasks, there must be at least n intervals that CPU are doing different tasks or just be idle.

You need to return the least number of intervals the CPU will take to finish all the given tasks.

Example 1:

Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.

Note:

1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].

———————————————————————————————————————————————————

Solution:

题意：模拟CPU的任务调度。给定一组字符数组和数值n，字符数组中每个字符表示一种任务，每个任务需要一个单位时间完成，n表示相同任务之间必须有n个单位时间间隔着。求完成所有任务需要的时间。

思路：以下是我的做法：耗时比较严重，在submissions上高达接近500ms

bool cmp(pair<char, int> a, pair<char, int> b) {
    return a.second > b.second;
}
class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        // n == 0：任务总数
        // n >= 任务种类 - 1：n * 任务最大个数
        // n < 任务种类 - 1：每次取最大任务数的处理，判断该计数器是否到达n，若未到达则取下一个最大的以此类推，都没有则idle，有则对应任务数-1，计数器重置
        
        if (n == 0)
            return tasks.size();
        
        map<char, int> taskIndex;
        for (int i = 0; i < tasks.size(); i++) {
            if (taskIndex.count(tasks[i]) == 0)
                taskIndex[tasks[i]] = 1;
            else
                taskIndex[tasks[i]]++;
        }
        vector<pair<char, int>> v;
        for (map<char, int>::iterator iter = taskIndex.begin(); iter != taskIndex.end(); iter++) {
            v.push_back(make_pair(iter->first, iter->second));
            // 将taskIndex 作为计数器（保存上一个相同元素出现时的intervals）
            iter->second = -1;
        }
        // 依任务数降序排序
        sort(v.begin(), v.end(), cmp);
        
        
        //if (n >= v.size() - 1)
        //    return n * v[0].second;
        
        int intervals = 0;
        while (v[0].second != 0) {
            /*
            for (int i = 0; i < v.size(); i++)
                cout << v[i].first << " " << v[i].second << " " << taskIndex[v[i].first] << endl;
            cout << endl;
            */
            bool flag = false;
            for (int i = 0; i < v.size(); i++) {
                if (taskIndex[v[i].first] != -1 && intervals - taskIndex[v[i].first] <= n) {
                    ;
                } else {
                    taskIndex[v[i].first] = intervals;
                    v[i].second--;
                    flag = true;
                    break;
                }
            }
            if (flag)
                sort(v.begin(), v.end(), cmp);
            intervals++;
        }
        return intervals;
    }
};

以下是Solution的最优解法：两张图即可说明清楚题意：

以及它的Java实现：时间复杂度为O(n)，空间复杂度为O(1)

public class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] map = new int[26];
        for (char c: tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n;
        for (int i = 24; i >= 0 && map[i] > 0; i--) {
            idle_slots -= Math.min(map[i], max_val);
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;
    }
}

其实对比下来，我的想法和Solution的想法原理上是一致的，但是Solution却加入了图表的形式更有利于分析问题本质，更容易找到更快捷的方法（+，-法），省去了我无谓的各种标记排序的方法。这是这道题我学到的东西，值得深思~