java - 要执行的最大任务数
问题描述
我陷入了一个问题。我知道 dp 可以在这里应用,但没有得到它。
考虑从 开始0
和结束的正数线的一部分10^9
。您开始时0
,可以执行 N 个任务。
ith
任务已经完成并且l[i]
需要t[i]
时间来执行。要执行ith
任务,您必须到达该点l[i]
并在该位置花费时间t[i]
。
在路径上移动一个单位需要一秒钟,即从 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
解决方案
有一个最佳解决方案,我们从 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