求解某区间最大总长度的O（n logn）动态规划问题

Question

给出了N间隔A_i= [S_i, F_i]表示每个间隔的开始和结束时间。所有间隔的开始和结束时间是不同的。我们想要maximize total length个中午相互重叠的选定时间间隔

问题1）使用O（n log n）时间，该问题的DP逻辑是什么？

问题2）是否等于加权间隔计划，以便权重成为间隔的长度

Answer 1

因为你的问题中提到了maximize total length。 实际上，经典的间隔调度算法适用于maximum count而不是maximum length 因此，没有一种选择总是有效的

您需要按F_i对A_i进行排序，然后在每个步骤中按照从i=0到n的动态方法计算A_0到A_i的最大和间隔如果您要计算A-i+1，有两种情况A_i+1与上一步中找到的最大和没有重叠，然后将其添加到和中，否则如果有重叠，则找到所有与A_i重叠的A_iA-i+1和O（lgn）（二进制搜索）并移除它们，然后比较f（k）+A_i+1和A_i，决定是否保留A_i+1