java—要执行的最大任务数

yruzcnhs 于 2021-08-25 发布在 Java

关注(0)|答案(1)|浏览(297)

我遇到了一个问题。我知道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

Java Arrays data-structures Algorithm dynamic-programming

来源：https://stackoverflow.com/questions/68259227/maximum-number-of-tasks-to-be-performed

1条答案

按热度按时间

tvokkenx1#

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

赞(0）回复(0）举报 2021-08-25

我来回答

java—要执行的最大任务数

1条答案

相关问题

热门标签

最新问答