执行每个类别一项任务的最短时间（具有不同的发布时间）

Question

我最近参加了一个 OA，其中您需要编写一个算法来查找您能够完成每个类别中的一项任务的最早时间。每个任务都有一个持续时间和可用时间（发布时间）。您需要按顺序完成任务。

输入示例：

// There could be more than 2 tasks in a category, this is just an example.
// The OA had only two categories, but I think a good solution would be able to handle an arbitrary amount.

catOneReleaseTime = [1, 4] // release times of the two tasks in category one
catOneDuration = [3, 2]    // duration times of the two tasks in category one

catTwoReleaseTime = [5, 2]
catTwoDuration = [2, 2]

我认为，问题的难度在于事情可能会重叠。

我怀疑这要么是动态规划问题，要么是贪心算法问题，但是，坦率地说，我真的不知道如何解决它。有些东西告诉我我也需要进行某种排序，但我不知道，因为我需要排序两个维度。在OA的时候，我用蛮力解决了一半，但我无法得到满分，因为我的解决方案在某些测试用例上会超时。

请注意，虽然这确实看起来与这些 Leet Code 问题相似，但我认为两者都不是：

• 2589。完成所有任务的最短时间
• 1723。找到完成所有工作的最短时间

Answer 1

使用 2 个类别，您可以在 O(n + m) 内解决它，我很确定您不会比这更好：

1. 计算两个类别的最快结束时间

2. 从其他类别最快结束时间开始计算最快结束时间，返回较小的值

这样就避免了排序，任务只是迭代了两次。