[每日一题] 2589.完成所有任务的最少时间

Richard

2024 年 05 月 15 日

112 次浏览

暂无评论

2075字数

LeetCode

> 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` 个时间从右往左依次放在区间内没有运行的时间点上，保证后续的任务尽量用到先前任务的运行时间。

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

```c++
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` 是按照结束时间排序后的，所以可以用二分查找找到每个任务区间内的时间点数目。

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)$ 。

最后修改：2024 年 05 月 15 日