Readme

2589.Minimum-Time-to-Complete-All-Tasks

解法1：

我们将所有任务按照end排序。这是因为end早的任务我们必然先考虑，其它没有到deadline的任务都可以放一放。对于第一个任务，我们必然会尽量拖延它的启动时间，即实际的运作时段是[end-duration+1, end]，这样就可以与后面的任务有更多的重合时间。对于第二个任务，必然会充分利用它与第一个任务实际工作的重合部分，假设已经重合的时间不够完成第二个任务，那么我们会在什么时段继续工作呢？其实也是同理，就是卡在第二个任务的deadline之前完成，目的也是为了尽量拖延，增加与后面的任务重合的概率。依此贪心的策略，就可以处理所有的任务。

因为本题的数据量不多，任务的个数n <= 2000，另外整体的时间跨度也不大1 <= starti, endi <= 2000，所以本题可以通过在时间轴上的遍历来暴力解决。比如对于某个任务[start,end,duration]，我们先看时间轴上哪些时刻是标记为开工的，与它的重合部分有多长，再与duration比较还得需要多长时间diff才能完成。如果T大于零，那么我们就从end开始往前遍历，将没有在工作的时刻标记为开工，直至把diff都消耗完。

这样的时间复杂度是O(N*T)。

解法2：

上述算法的时间复杂度其实可以不依赖于总时间跨度T。可以想象，如果每个任务的时间跨度都很大，那么遍历时间轴的效率是很低的。上述的算法可以用o(nlogn)来实现。

在上述算法里，我们依次处理每个任务的时候，其实都会在时间轴上确定下一段段的实际开工时间，它们是一系列互不重叠的区间。所以我们用arr来盛装这些区间，对于每个区间我们用[a,b,totalTime]表示，a表示起点、b表示终点（都是双闭区间），totalTime表示该区间结束时整个时间轴上已经开工时间的总和，相当于arr里开工区间的长度的前缀和。

对于一个新任务[start,end,duration]，我们先要计算新区间与已经开工的这些区间有多少重合度overlap。因为有了前缀和的信息，所以这个计算是可行的。我们只需要用二分法，定位start在arr里的位置，找到最后一个早于start的区间interval。如果此interval与新任务完全不重合，那么新任务与已开工的重合度overlap就是interval右边的所有开工区间的长度，这可以用两个前缀和之差得到。如果此interval与新任务有重合部分，那么overlap就是前一种情况的计算结果，再加上此区间与[start,end]的重合部分。

我们知道了duration和overlap，就可以知道我们还需要从end开始往前填充若干个开工区间之间的间隔，以满足额外的开工长度diff，显然这会导致arr最后的几个开工区间合并起来。所以我们就暴力从后往前枚举每个区间[a,b]，思路如下：

1. 如果融合了该区间，那么我们新增了多长的开工时间（新增的开工时间其实是该区间与下一个区间之间的间隔长度）
2. 如果新增的开工时间大于diff，那么说明该区间不用被重合，我们只需要计算该区间右端点后的某个位置x，将[x,end]加入arr即可。
3. 如果新增的开工时间小于diff，那么说明该区间需要被融合，我们将arr的最后一个区间重置为[a,end]. 更新diff后开启下一个循环。

最终的总开工时间就是arr里最后一个区间对应的前缀和。