c++ - 通过安排任务最大化分数

Question

所以我们有一个 T 天的时间表，其中必须执行一些任务。每个任务都有一个惩罚分数。如果任务没有在给定的时间线内执行，它的分数加起来就是最终的惩罚分数。每项任务只能在给定开始时间后执行。

输入的格式为:

T

分数 Quantity_of_task Starting_time

例如:

T = 10

140 5 4

这意味着从第 4 天起必须执行 5 个惩罚分数为 140 的任务。您在某一天最多可以执行 1 项任务。

目标是最小化最终的罚分。

我尝试做的事情:

Example - 
T = 10

Input size = 5

150 4 1                                                                     
120 4 3                                                                                                                                                 
200 2 7                                                                                                                                                                                                
100 10 5                                                                                                                                                                              
50 5 1

我根据惩罚分数对列表进行排序，贪心将惩罚分数高的任务分配到相应的日期，即

得分最高为 200 的 2 个任务被分配到第 7 天和第 8 天

下一个最高得分为 150 的 4 个任务被分配到 1、2、3、4 天

下一个最高分 120 的 4 个任务被分配到 5、6、9、10 天

它给出了时间表150 150 150 150 120 120 200 200 120 120

遗漏的任务:

10 分 100 分的任务 = 1000 罚分
5 个任务，50 分 = 250 罚分

最终罚款 = 1250。

这需要 O(T * input_size)。有没有更优雅和优化的方式来做到这一点？

输入大小和 T 都有 10^5 的约束。

谢谢。

Answer 1

如果您将可用天数存储在一个有序集中，那么您可以更快地执行您的算法。

例如，C++ 提供了一个带lower_bound 的有序集。将在 O(logn) 时间内找到开始时间后第一个可用日期的方法。

总的来说，这应该给出一个 O(nlogn) 算法，其中 n = T+input_size。

例如，我怀疑当您从第 3 天开始分配 4 个惩罚为 120 的任务时，您当前的代码将在第 3、4、5 天等循环。直到找到未分配的日期。您现在可以将这个 O(n) 循环替换为对 lower_bound 的单个 O(logn) 调用以查找第一个未分配的日期。当你贪婪地分配日期时，你也应该从集合中删除它们，这样它们就不会被分配两次。

请注意，只有 T 天，因此最多会有 T 天的作业。例如，假设所有任务的开始时间为 1，数量为 T。那么第一个任务将花费 O(Tlogn) 时间来分配，但所有后续任务只需要一次调用 lower_bound(因为没有剩余天数可以分配), 所以每次都需要 O(logn)。