Leetcode621. 任务调度器

Every day a Leetcode

题目来源：621. 任务调度器

类似题目：1953. 你可以工作的最大周数

解法1：贪心

本质上来说，我们需要构造一个尽量短的，相同元素间隔 >= (n+1) 的序列。

用一个数组 cnt 统计每个任务的次数。设 cnt 的元素和为 s，这是任务总数，也是序列长度的下界。

当存在多个任务时，由于每一类任务都需要被完成，因此本质上我们最需要考虑的是将数量最大的任务安排掉，其他任务则是间插其中。设 mx=max⁡(cnt)，共有 mxCnt 个任务数为 mx 的任务。我们可以把该任务的阶段任务每次间隔 n 位排列在序列中，其他的任务则安排在空位上，这样的构造方法能保证序列最短。

假设 mx = 4，mxCnt = 3，n = 4，安排情况如下所示：

构造方法是：前面 (mx - 1) 行，每行 (n + 1) 个元素，最后加上 mxCnt 个元素，序列的长度为 (mx - 1) * (n + 1) + mxCnt。

当 s <= (mx - 1) * (n + 1) + mxCnt 时，我们总能将其他任务插到空闲时间中去，不会引入额外的冻结时间；否则，我们就要在序列中插入空位。

综上，答案是 s 和 (mx - 1) * (n + 1) + mxCnt 的较大值，即 max(s, (n + 1) * (mx - 1) + mxCnt)。

代码：

/*
 * @lc app=leetcode.cn id=621 lang=cpp
 *
 * [621] 任务调度器
 */

// @lc code=start
class Solution
{
public:
    int leastInterval(vector<char> &tasks, int n)
    {
        vector<int> cnt(26, 0);
        for (char &task : tasks)
            cnt[task - 'A']++;

        int mx = *max_element(cnt.begin(), cnt.end());
        int s = 0, mxCnt = 0;
        for (int &c : cnt)
        {
            s += c;
            if (c == mx)
                mxCnt++;
        }

        return max(s, (n + 1) * (mx - 1) + mxCnt);
    }
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n+|∑|)，其中 n 是数组 tasks 的长度，∑ 是字符集，因为数组 tasks 全是大写英文字母，所以 |∑| = 26。

空间复杂度：O(|∑|)，其中 ∑ 是字符集，因为数组 tasks 全是大写英文字母，所以 |∑| = 26。