要执行的最大任务数
要执行的最大任务数
提问于 2021-07-05 16:15:52
我遇到了一个问题。我知道dp可以在这里应用，但不能实现。
考虑从0开始，以10^9结尾的正数行的一部分。从0开始，可以执行N个任务。
ith任务位于l[i]，需要执行t[i]时间。要执行ith任务，您必须到达l[i]点，并在该位置花费时间t[i]。
在路径上运行一个单位需要1秒，即从1到3将需要(3-1)=2秒。
给你T秒的时间，在这段时间里，你必须尽可能多地执行任务，然后回到开始的位置。我需要找出最大的时间可以执行T。
示例
考虑M= 3，T= 10，l[] = 1，2和t[] = 3，2。
如果我们执行第一项任务，所消耗的总时间是1(旅行)+3(完成任务)= 4，剩下的时间是10-4= 6。
现在，如果我们连续地执行第二项任务，总时间是1(从1开始)+2(完成任务)= 3，剩下的时间是6- 3 =3。
如果我们从2返回到0。总时间为2，剩余时间为3-2= 1，因此我们可以在给定的时间内安全地完成这两项任务。答案是2。
约束很高：
1 <= N <= 10 ^ 5
0 <= T <= 10 ^ 8
0 <= l[i], t[i] <= 10 ^ 9回答 1
Stack Overflow用户
回答已采纳
发布于 2021-07-05 16:44:25
这里有一个最优解，我们从0到某个坐标x并返回，贪婪地选择区间0，x从最短到最长的任务。
可能有一个动态编程解决方案，但这不是我首先要达到的。相反，我会使用一种扫描线算法，将x从0增加到T/2，从而保持最优解。当x通过l[i]时，我们将任务i添加到议程中。每当目前的议程花费太多时间，我们就放弃最长的任务。
在Python (未经测试)中，该算法看起来类似于此。
import heapq
def max_tasks(T, l, t):
x = 0
heap = []
opt = 0
# Sweep the tasks left to right
for l_i, t_i in sorted(zip(l, t)):
# Increase x to l_i
T -= 2 * (l_i - x)
x = l_i
# Add task i to the agenda
T -= t_i
# This is a min-heap, but we want the longest tasks first
heapq.heappush(heap, -t_i)
# Address a time deficit by dropping tasks
while T < 0:
if not heap:
# Travelled so far we can't do any tasks
return opt
# Subtract because the heap elements are minus the task lengths
T -= heapq.heappop(heap)
# Update the optimal solution so far
opt = max(opt, len(heap))
return opt页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/68259227
复制相关文章
相似问题
腾讯云开发者
