加权区间调度的一种变型

Question

我试图解决一个优化问题，它最终归结为:给定一组加权区间S，我试图找到S中的最小区间数，使它们跨越预定义的、假设更大的区间I，并具有最大权重。首先，看起来我们可以将集合覆盖问题简化为这个问题，但是区间的连续性意味着集合也必须是“连续的”？或者这个问题是多目标的？

Answer 1

这个问题至少允许一个简单的动态编程解决方案。

考虑您的线段的所有端点。按坐标对它们进行排序。

对于每个端点X，计算覆盖从I开始(将此开始表示为S)到此点X的整个间隔的最小分段数。如下所示:迭代覆盖X点的所有线段。对于每个细分市场，尝试将其应用到您的解决方案中。然后你必须用最少的段数覆盖从S到这个段开始的间隔，并且用最大的权重覆盖所有这样的解决方案-你在前面的动态编程中已经计算过这个答案了。因此，在迭代完所有部分之后，只需选择最佳解决方案即可。

类似于(伪代码)

crop all given segments if they stretch outside of I, now each segment lies in I
sort all endpoints of your segments, assume X is the sorted array and L its length
if (X[0]!=I.left) or (X[L]!=I.right)
    no solution is availavle
answer[0] = 0
weight[0] = 0
for i=1..L
    answer[i] = infinity
    for j=0..N (the number of segments)
        if (X[i]>=segment[j].left) and (X[i]<=segment[j].right)
            p = position of segment[j].left in X (can be precalculated)
            candidate_answer = answer[p] + 1
            candidate_weight = weight[p] + segment[j].weight
            if (candidate_answer<answer[i]) or (
                  (candidate_answer==answer[i]) and (candidate_weigth>weight[i]))
                answer[i] = candidate_answer
                weight[i] = candidate_weight
answer[L] and weight[L] is your answer

这是O(N^2)。也许有一个更快的解决方案，但我现在想不出一个。