https://leetcode.cn/problems/minimum-time-to-complete-all-tasks/description/?envType=daily-question&envId=2024-05-06

贪心

观察题目最多只有 2000 个任务，时间最大也为 2000，所以可以使用暴力法求解。对结束时间从小到大排序，使用一个数组 isRun 记录每个时间点电脑是否有在运行。每个时间范围都统计一个运行时间数 total ，设该时间区间需要运行 duration 秒，则：

• total >= duration 时，该任务可以和之前的任务一起运行，无需占用额外的时间。
• total < duration 时，需要增加 duration - total 个时间点。此时可以将 duration - total 个时间从右往左依次放在区间内没有运行的时间点上，保证后续的任务尽量用到先前任务的运行时间。

最后返回总运行时间即可。

class Solution {
public:
    int findMinimumTime(std::vector<std::vector<int>> &tasks) {
        std::sort(tasks.begin(), tasks.end(), [&](std::vector<int> &a, std::vector<int> &b) { return a[1] < b[1]; });
        std::vector<bool> isRun(tasks.back()[1] + 1);

        int need, res = 0;
        for (auto &task : tasks) {
            need = task[2] - std::count(isRun.begin() + task[0], isRun.begin() + task[1] + 1, true);
            if (need < 0)
                continue;

            res += need;
            for (int i = task[1]; need > 0; i--) {
                if (!isRun[i]) {
                    isRun[i] = true;
                    need -= 1;
                }
            }
        }

        return res;
    }
};

• 时间复杂度：$O(m \cdot n)$ ，其中 $n$ 为数组 tasks 的大小，$m$ 是 tasks 中结束时间的最大值。
• 空间复杂度：$O(m)$ 。

栈 +二分查找优化

前面的 isRun 数组可以使用栈来优化，记录下每个电脑开机的区间，并且将连续的区间合并。同时记录每个区间的总运行时间长度 (前缀和) 。

因为 tasks 是按照结束时间排序后的，所以可以用二分查找找到每个任务区间内的时间点数目。

class Solution {
public:
    int findMinimumTime(std::vector<std::vector<int>> &tasks) {
        std::sort(tasks.begin(), tasks.end(), [&](std::vector<int> &a, std::vector<int> &b) { return a[1] < b[1]; });
        std::vector<std::array<int, 3>> run{{-1, -1, 0}};

        for (auto &task: tasks) {
            auto former = *--std::lower_bound(run.begin(), run.end(), task[0],
                                         [&](std::array<int, 3> &element, const int &value) {
                                             return element[0] < value;
                                         });

            int lack = task[2] - run.back()[2] + former[2];
            if (task[0] <= former[1])
                lack -= former[1] - task[0] + 1;

            if (lack <= 0)
                continue;

            auto latest = run.back();
            while (task[1] - latest[1] <= lack) {
                lack += latest[1] - latest[0] + 1;
                run.pop_back();
                latest = run.back();
            }

            run.push_back({task[1] - lack + 1, task[1], latest[2] + lack});
        }
      
        return run.back()[2];
    }
};

• 时间复杂度：$O(nlogn)$ ，其中 $n$ 为 tasks 数组的长度。
• 空间复杂度：$O(n)$ 。