您提到，您可以将活动划分为不重叠的集群，即使其中的活动已转移到一定程度。这些集群中的每一个都可以独立考虑，为每个集群计算的最佳结果可以简单地总结为最终答案。因此，该算法的第一步可能是试运行，将所有活动扩展到两个方向，找到哪个活动形成集群，并独立处理每个集群。在最坏的情况下，所有活动都可能形成一个集群。

根据剩余群集的最大大小，有几种方法。如果小于20（或者甚至小于30，取决于您希望程序在几秒钟还是几分钟内运行），则可以使用贪婪的方法将对给定集群中所有活动子集的搜索结合起来。换句话说：如果您正在处理N个元素的子集，请尝试每个2^N个可能的子集（好的，2^N-1，如果我们忘记了空的子集），请检查该特定子集中的活动是否可以以非重叠的方式进行调度，并选择合格且具有最大和的子集。

我们如何检查活动的给定子集可以以非重叠方式进行安排？让我们按照它们的升序对其进行排序，并从左到右对其进行处理。对于每项活动，我们都会尽早安排它，以确保它与我们已经考虑过的活动不交叉。因此，群集中的第一个活动总是比原计划提前t的时间开始，第二个活动要么在第一个活动结束时开始，要么比原计划的时间t早，以较大者为准，并且以此类推。如果在任何时候我们都无法以与上一个活动不重叠的方式安排下一个活动，那么就没有办法以非重叠的方式安排该子集中的活动。该算法需要O(NlogN) time，并且总体上每个集群都在O(2^N * NlogN)中进行处理。再一次，请注意此功能的增长非常快，因此，如果要处理足够大的群集，则此方法不可用。

===

另一种方法特定于您提供的其他限制。如果活动的开始和结束并且参数t都是以整数秒为单位来度量的，并且t大约是2分钟，则每个群集的问题都放在一个小的离散空间中。即使您可以将任务定位为从非整数第二个值开始，但总会有一个仅使用整数的最佳解决方案。 （要证明这一点，请考虑一个不使用整数的最佳解决方案-由于t是整数，因此您始终可以将任务从最左边开始向左移动一点，以便它从整数值开始。）

知道开始时间和结束时间是离散的，您可以构建一个DP解决方案：按照活动的结束顺序*对其进行处理，并记住从前1个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第2个，第三个...，如果给定活动在时间x结束，则从activity_start - t到activity_start + t的每个x N个活动。如果我们将该记忆功能表示为f[activity][end_time]，则重复关系为f[a][e] = weight[a] + max(f[i][j] over all i < a,j <= e - (end[a] - start[a])，这大致翻译为“如果活动a在时间e结束，则先前的活动必须具有在a的开头或结尾处结束-因此，让我们选择上一个活动及其结尾的最大总权重，然后加上当前活动的权重。”

*同样，我们可以证明至少有一个最优答案可以保留此排序，即使可能还有其他不具有此属性的最优答案

我们可以走得更远，并消除先前活动的迭代，而是将这些信息编码在f中。然后，其定义将更改为“ f[a][e]是前a个活动的最大可能总权重，如果它们在e之后都没有结束”，则重复关系将变为f[a][e] = max(f[a-1][e],weight[a] + max(f[a-1][i] over i <= e - (end[a] - start[a])])) ，其计算复杂度为O(X * N)，其中X是放置任务开始/结束的离散空间的总跨度。

我假设您不仅需要计算最大可能的重量，还需要计算选择以获得最大重量的活动，甚至可能需要精确地计算每个活动的开始时间。值得庆幸的是，我们可以从f的值中得出所有这些值，或者在计算f的同时对其进行计算。后者更容易推论，因此让我们介绍第二个功能g[activity][end]。 g[activity][end]返回一对(last_activity,last_activity_end)，从本质上为我们指出了f[activity][end]中最佳权重所使用的确切活动及其时机。

让我们看一下您提供的示例以说明其工作原理：

(start,end,profit)
a1: 10 12 120
a2: 10 13 100
a3: 14 18 150
a4: 14 20 100
a5: 120 125 100
a6: 120 140 150
a7: 126 130 100

1. 我们在活动结束时对其进行排序，从而交换a7和a6。
2. 我们为第一个活动初始化f和g的值：

f[1][7] = 120,f[1][8] = 120,...,f[1][17] = 120，这意味着第一个活动可能会在7到17之间结束，费用为120。所有其他f[1][i]的{​​{1}}应该设置为0。

i，这意味着g[1][7] = (1,7),g[1][8] = (1,8),g[1][17] = (1,17)值中包含的最后一个活动是f[1][i]，并在a1处结束。 i以外的所有g[1][i]的{​​{1}}是未定义/不相关。

1. 那是一些有趣的开始的地方。对于每个i不能在时间[7,17]结束的i，让我们分配a2，这实际上意味着我们不会在其中使用活动i答案。对于所有其他f[2][i] = f[1][i],g[2][i] = g[1][i]，即在a2间隔中，我们有：

i

[8..18]

f[2][8] = max(f[1][8],100 + max(f[1][0..5])) = f[1][8]。这是第一次，第二个子句不只是纯100，例如f[2][9] = max(f[1][9],100 + max(f[1][0..6])) = f[1][9]。实际上，它是f[2][10] = max(f[1][10],100 + max(f[1][0..7]))，这意味着我们可以进行活动f[1][7]>0，以使其在时间100+f[1][7]=220结束的方式进行移动，并获得总权重{{1 }}。我们将以这种方式继续为所有a2计算10。

220的值为：f[2][i]，i <= 18，g，因为最佳选择活动g[2][8]=g[1][8]=(1,8)并在时间{{ 1}}。

我希望这种情况如何继续下去的模式是可见的-我们计算出g[2][9]=g[1][9]=(1,9)和g[2][10]=(2,10)的所有值，直到最后，然后在所有可能的结束时间内选择最大的a2最近一次活动的10。借助辅助功能f，我们可以向后遍历这些值以找出确切的活动和时间。即，我们使用的最后一个活动及其时间位于g中。我们称它们为f[N][e]和e。我们知道A从g开始。然后，先前的活动必须在该时刻或之前结束-因此，让我们看一下g[N][e]，依此类推。

请注意，即使您没有将任何内容划分为集群，该方法仍然有效，但是通过该划分，可以减少计划任务的空间大小以及运行时的大小。

您可能会注意到，这些解都不是输入大小的多项式。我感觉到您的问题没有通用的多项式解，但是我无法通过将另一个NP完全问题简化为证明。阅读还原/更好的通用解决方案真的很好奇！