LeetCode·621.任务调度器·构造法

链接：https://leetcode.cn/problems/task-scheduler/solution/by-xun-ge-v-akns/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路
按照此图进行构造即可

题目要求相同的任务中间需要休息n个单位，我们想要在最短的时间内完成所有任务，那么就需要在相同任务的n个单位休息中添加其他任务，来消耗休息时间，我们取相同任务最多为构造最长边，因为相同任务需要休息n个单位，那么休息时间最长的就是相同任务最多的。

这里主要优化一下过程，我们在计算任务数时，就已经对最多最小的任务进行了计算，那么我们只需要设置两个变量，统计一下最多任务数和最多任务数的个数即可，不需要额外再对这些变量进行统计

代码

#define MAX(a , b) ((a) > (b) ? (a) : (b))
int leastInterval(char* tasks, int tasksSize, int n){
    int str[26];
    memset(str, 0, sizeof(int) * 26);//初始化
    int max = -1;
    int cunst = 0;
    for(int i = 0; i < tasksSize; i++)//遍历任务数组
    {
        str[tasks[i] - 'A']++;
        if(max < str[tasks[i] - 'A'])//统计最大值
        {
            max = str[tasks[i] - 'A'];
            cunst = 1;
        }
        else if(max == str[tasks[i] - 'A'])//最大值相同数+1
        {
            cunst++;
        }
    }
    
    return MAX(((max-1)*(n+1)+cunst) , tasksSize);
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/task-scheduler/solution/by-xun-ge-v-akns/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度