LeeCode 621.任务调度器

文章目录

题目内容：

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

解题思路：

从题目内容可以得知对最多26个任务进行调度，每个任务的冷却时间为n;因此使用两个长度为26的整形数组ha和de，其中ha的第i个数组元素代表(i+‘A’)任务的剩余执行次数，de的第i个元素记录(i+‘A’)任务的剩余冷却时间。同时为了保证最短的时间，在每次取任务时，保证取得的任务是当前剩余任务中需要执行的次数最大的。

解题代码：

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        int ha[26] = { 0 };
        int de[26] = { 0 };
        int i = 0;
        while (i < tasks.size())
        {
            ha[tasks[i] - 'A']++;
            i++;
        }
        i = 0;
        while (i < 26)
        {
            de[i] = 1;
            i++;
        }
        int res = -1;
        while (1)
        {
            int j = 0;
            i=0;
            res++;
            while (i < 26)
            {
                if(de[i])
                    de[i]--;
                i++;
            }
            int t = findtr(ha, de);
            if (t != -1)
                de[t] = (n+1);
            else
            {
                int k = 0;
                while (k < 26)
                {
                    if (ha[k])
                        break;
                    k++;
                }
                if (k == 26)
                    return res;
            }
        }
    }
    int findtr(int* ha, int* de)
    {
        int i = 0;
        int max = 0;
        int temi = -1;
        while (i < 26)
        {
            if (ha[i] > max)
            {
                if (de[i] == 0)
                {
                    max = ha[i];
                    temi = i;
                }
                else
                {
                    i++;
                    continue;
                }
            }
            i++;
        }
        if(temi>-1)
            ha[temi]--;
            return temi;

    }
};