要执行的最大任务数

Question

我遇到了一个问题。我知道这里可以应用dp，但是没有得到。

考虑从 0 开始到 10^9 结束的正数线的一部分。你从0开始，有N个任务可以执行。

ith 任务在 l[i]，需要 t[i] 时间才能执行。要执行 ith 任务，您必须到达 l[i] 点并在该位置花费时间 t[i]。

在路径上行驶一个单位需要一秒钟，即从 1 到 3 需要 (3 - 1) = 2 秒。

你有 T 秒的时间，在这段时间内你必须执行尽可能多的任务并且 return 到起始位置。我需要找到可以在时间 T 内执行的最大值。

例子

考虑 M = 3，T = 10，l[] = [1, 2]，t[] = [3, 2]。

如果我们执行第一个任务，总消耗时间为 1（旅行）+ 3（完成任务）= 4。剩余时间为 10 - 4 = 6。

现在，如果我们连续执行第 2 个任务，总时间为 1（从 1 开始）+ 2（完成任务）= 3。剩余时间为 6 - 3 = 3。

现在如果我们 return 从 2 到 0。总共花费的时间是 2。剩余时间是 3 - 2 = 1。因此我们可以在给定的时间内安全地完成这两项任务。所以答案是2.

约束条件高：

1 <= N <= 10 ^ 5
0 <= T <= 10 ^ 8
0 <= l[i], t[i] <= 10 ^ 9

Answer 1

有一个最佳解决方案，我们从 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

要执行的最大任务数

Maximum number of tasks to be performed

java

arrays

algorithm

dynamic-programming

data-structures