在给定的开始时间和持续时间内查找任务结束顺序的算法

Question

我最近参加了一个面试，有人问我这个问题：

给定数组中的开始时间：[1,2,3,2]及其持续时间[3,4,4,3]

查找并返回任务完成的顺序。对于这个例子，结束时间是：[4,6,7,5]，所以返回的值应该是[1,3,4,2]。

我的方法/解决方案：

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

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

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

请提出更好的解决方案。在面试中（使用白板和记号笔），如果没有错误，很难实现这种方法。如果没有更好的解决方案，最简单的方法是什么。更好的解决方案=更好的时间复杂性。

Answer 1

最简单快捷的解决方案

创建两个阵列：

最终时间数组：[4,6,7,5]

索引数组：[0,1,2,3]

使用快速排序对最终时间数组进行排序（或者插入排序，如果可以确定，数组将非常小=小于10个数字），每当切换最终时间数组元素时，也要切换索引数组。

当finaltime排序时，索引数组保存结果。

Answer 2

假设您的原始集合（如数组）创建如下（显然是伪代码）：

create collection first[] with elements (starttime, duration)
first.append (1, 3)
first.append (2, 4)
first.append (3, 4)
first.append (2, 3)

这将为您提供（开始时间，持续时间）元组first=[（1,3), (2,4), (3,4), (2,3)]的集合。

然后，你可以用一个单独的结构来做你想做的事情，这个结构只包含两件事情：

• 该指数反映了当前的结构

首先，填充这个新结构的数组second，使索引与原始数组first匹配，如下所示：

create array second[] with elements (firstindex, endtime)
for each index in first.indexes:
    second.append (index, first[index].starttime + first[index].duration)

这将为您提供（firstindex，endtime）元组的集合second=[（1,4）、（2,6）、（3,7）、（4,5）]（这里我们假设集合是基于一而不是基于零的）。

然后根据结束时间对second数组进行排序，得到second=[（1,4）、（4,5）、（2,6）、（3,7）]。

然后，您可以在完成顺序的任务代码如下：

for each index in second.indexes:
    output "task # ", second[index].firstindex
    output " starts at, " first[second[index].firstindex].starttime
    output " duration, " first[second[index].firstindex].duration
    output " ends at ", second[index].endtime, new-line

其结果将是：

task # 1 starts at 1 duration 3 ends at 4
task # 4 starts at 2 duration 3 ends at 5
task # 2 starts at 2 duration 4 ends at 6
task # 3 starts at 3 duration 4 ends at 7

Answer 3

免责声明：我的回答基于这样一个想法，即这个问题不经过任何排序就无法解决

老实说，你解决这个问题的办法听起来不错。这个问题描述了结果应该按一定的顺序排列，这意味着不可能找到比O（n log n）更快的解决方案。

这是因为众所周知，不可能存在一种算法或程序能够对复杂度小于O（n logn）的可排序元素列表进行排序。

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

如果你真的要实现这一点，只需练习几次。