Task Scheduler

题目描述

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.

思路分析

这题目可以用贪婪算法实现，基本思想是：先计算出每个task出现的频数存入number容器中，再将所有频数按降序调用sort排好序后存入queue容器中，并计算出现频数最高的task的种类Largest。将频数最高的task按照间隙分布，于是会有（queue[0]-1）个间隙，再往间隙中插入频数递减的task，每次在一个间隙中插入一个task，从左往右循环插入，可分为两种情况讨论：

• task可以填充时间间隙，则CPU所花的最短时间是task的个数；

• task不能完全填充时间间隙，需要补充idle，则CPU所花的最短时间是(queue[0]-1)*(n+1) + Largest

代码实现

class Solution {
public:
    static bool compare(const int& a, const int& b) {
        if (a >= b)
            return true;
        else 
            return false;
    }
    int leastInterval(vector<char>& tasks, int n) {
        int len = tasks.size();
        std::vector<int> number(26, 0);        //记录每个task出现的频数
        std::vector<int> queue;      //按频数大小排序

        for (int i = 0; i < len; i++) {
            number[tasks[i]-'A'] += 1;
        }
        for (int i = 0; i < 26; i++) {
            if (number[i] != 0)
                queue.push_back(number[i]);
        }
        sort(queue.begin(), queue.end(), compare);

        int Largest = 0;    //最高频数的task类型数
        for (int i = 0; i < queue.size(); i++) {
            if (queue[i] == queue[0])
                Largest += 1;
            else break;
        }

        int count = 0;      //总时间数
        //除去频数最高的tasks，剩余tasks不能补全时间间隔
        int temp = (queue[0]-1)*(n+1) + Largest;
        if (len >= temp)
            count = len;
        else 
            count = temp;
        return count;
    }
};