java - 在给定开始时间和持续时间的情况下查找任务结束顺序的算法

Question

我最近参加了一个采访，有人问我这个问题:

数组中的给定开始时间:[1, 2, 3, 2]以及它们的持续时间 [3, 4, 4, 3]

查找并返回任务完成的顺序。对于此示例，结束时间为:[4, 6, 7, 5] 因此返回的值应为 [1, 3, 4, 2]。

我的方法/解决方案:

创建一个数据结构来将每个类表示为具有以下属性的任务对象:

1. 开始时间
2. 结束时间
3. 持续时间
4. 完成索引

然后根据每个对象的结束时间对数组进行排序。将每个元素与原始数组索引进行比较，并返回原始任务顺序中的完成索引。

请提出更好的解决方案。在采访中(使用白板和记号笔)很难在没有错误的情况下实现这种方法。如果没有更好的解决方案，最简单的方法是什么？更好的解决方案 = 更好的时间复杂度。

Answer 1

免责声明:我的回答基于这样的想法，即如果不进行任何排序就无法解决此问题

老实说，您对问题的解决方案听起来不错。该问题描述了结果应按一定顺序排列，这意味着不可能找到比 O(n log n) 更快的解决方案，保证。

这是因为众所周知，不存在可以对复杂度小于 O(n log n) 的可排序元素列表进行排序的算法或程序。

这意味着如果您的解决方案在 O(n log n) 中运行，则您的解决方案是最优的。如果我是你，我会在面试中提到你的解决方案的这个特性，因为它表明你不仅明白你解决了问题，而且知道没有比这更好的解决方案了。

如果您必须实际执行此操作，只需练习几次即可。