找到非重叠序列最大覆盖范围的算法。（即加权间隔调度问题）

Question

我有一个非常相似的问题 找到最长非重叠序列的算法.

与链接问题的唯一区别是，不是找到代表 最长序列, ，我需要找到代表 最大覆盖范围, ，我的意思是 元组长度之和 是最大值（a 元组长度 存在 last - first + 1 给定定义 元组 在下一句中）。

我以与链接问题不同的方式表示我的元组。代替 (starting index, length), ，我将我的元组表示为 (first, last);例如，元组 (3,7) 表示数字的集合 [3, 4, 5, 6, 7]. 。（一个元组 重叠 另一个元组，即使端点匹配；IE。， (2,6) 和 (6,8) 重叠 因此不能同时出现在解决方案中。）

作为示例，请考虑以下元组集，按以下顺序排序 first:

[(0,100), (2,50), (30,150), (60,95), (110,190), (120,150), (191,200)]

这里的最大集合是 [(0,100), (110,190), (191,200)] 覆盖范围为 101 + 81 + 10 = 192. 。（请注意，此解决方案中的元组是 不重叠.)

解决此问题的最简单算法的示例是什么？该算法的复杂性是多少？（如果这个问题能解决的话那就太好了 O(N), ，但目前不知道是否可以。）

附录： 回想起来，原来我在这里问的问题相当于 加权区间调度问题. 。这是一个特例 区间调度问题.

下面@j_random_hacker 的答案实际上是加权间隔调度问题的已知解决方案，其时间复杂度为 O(N log(N)).

Answer 1

这是一个 O(nlog n)-时间，O(n)-空间 算法。首先，如果元组数组尚未按此顺序排列，则按起始位置对元组数组进行排序。我将假设从零开始的数组索引。

我们将元组 i 的起始位置称为 b(i)，将结束位置称为 e(i)，因此它的总长度为 e(i) - b(i) + 1。另外，我们定义一个函数 next(i)，它返回可以出现在元组 i 右侧的第一个元组在元组列表中的位置。请注意，next(i) 可以通过二分查找在 O(log n) 时间内计算出来：只需将所有元组起始位置 b(i) 保留在数组 b[] 中，并在子数组 b[i+1 .. 中搜索第一个 j 。n-1] 具有 b[j] > e(i)。

让我们将 f(i) 定义为从以下位置开始的任何非重叠元组集的最大覆盖范围： 或之后 图普勒岛由于元组 i 本身要么在这个最优集中，要么不在这个最优集中，我们有：

f(i) = max(e(i) - b(i) + 1 + f(next(i)), f(i+1)) for 0 <= i < n

我们也有边界条件 f(n) = 0.

显然，最大可能的覆盖范围由 f(0) 给出。这很容易计算。在伪 C++ 中：

int b[] = /* Tuple beginning positions, in nondecreasing order */;
int e[] = /* Tuple end positions */;
int n = /* Number of tuples */;

// Find the array position of the leftmost tuple that begins to the right of
// where tuple i ends.
int next(int i) {
    return upper_bound(b + i + 1, b + n, e[i]);
}

int maxCov[n + 1];    // In practice you should dynamically allocate this

// After running this, maxCov[i] will contain the maximum coverage of any
// nonoverlapping subset of the set of n - i tuples whose beginning positions
// are given by b[i .. n-1] and whose ending points are given by e[i .. n-1].
// In particular, maxCov[0] will be the maximum coverage of the entire set.
void calc() {
    maxCov[n] = 0;
    for (int i = n - 1; i >= 0; --i) {
        maxCov[i] = max(e[i] - b[i] + 1 + maxCov[next(i)], maxCov[i + 1]);
    }
}

循环中 calc() 运行 n 次，每次迭代对二分搜索函数进行一次 O(log n) 调用 upper_bound().

我们可以通过计算 f(0) 的 max() 的两个输入来重构这个大小的实际集合，看看哪一个实际上产生了最大值，记录它是否意味着元组 0 的存在或不存在，然后递归处理余数（对应于 f(next(0)) 或 f(1)）。（如果两个输入相等，则存在多个最佳解决方案，我们可以遵循其中之一。）

Answer 2

下面的算法的工作原理是递归地检索每个元素是最左边成员的最大非重叠集合，然后返回具有最大覆盖范围的集合。请参阅代码中的注释。

用 PHP 实现。你可以在这里测试一下 http://viper-7.com/xowTRF

我认为这个算法的复杂度是 O(2^N) 或者 O(N^2) 对于缓存，如果您不同意，请随时发表评论。

$set = [[0,100], [2,50], [30,150], [60,95], [110,190], [120,150], [191,200]];
$GLOBALS['cache'] = array(); //cache for overlapping sub problems

function maximumSet($set) {

    if(count($set) === 1) {
        return $set;
    }

    $cache_key = [];

    foreach($set as $k) {
        $cache_key[] = implode($k,'.');
    }

    $cache_key = implode('_',$cache_key);

    if(isset($GLOBALS['cache'][$cache_key])) {
        return $GLOBALS['cache'][$cache_key];
    }

    $maximumResult = null;

    //for each element in the set,
    //get the largest non-overlapping set that the element is a member of
    //once all N sets have been computed, return the largest one
    foreach($set as $k => $element) {

        unset($set[$k]);

        //create a new set $copy, which contains the remaining elements that
        //do not overlap with $element            
        $copy = $set;

        foreach($set as $k2 => $element2) {
            if($element2[0] <= $element[1]) { 
                //element is considered non overlapping if its start 
                //is less than or equal to current element's end
                unset($copy[$k2]);
            }
            else break; //because the list is sorted we can break the 1st time
            //see a non-overlapping element
        }

        if(!empty($copy)) {
            //if there is at least one non-overlapping element
            //recursively get the maximum set
            $maximumSubset = maximumSet($copy);
            //prepend the current element to it
            array_unshift($maximumSubset,$element);
        }
        else {
            //otherwise the maximum non-overlapping set which contains this element
            //is the element itself                
            $maximumSubset = [$element];
        }

        //store the set in the results by coverage
        $coverage = getCoverage($maximumSubset);
        if(is_null($maximumResult) || $maximumResult['coverage'] < $coverage) {
            $maximumResult = [
                'coverage' => $coverage,
                'set' => $maximumSubset
            ];
        }
    }

    $GLOBALS['cache'][$cache_key] = $maximumResult['set'];
    return $maximumResult['set'];
}

function getCoverage($set) {
    $range = 0;
    foreach($set as $v) {
        $range += ($v[1] - $v[0]);
    }
    return $range;
}

$x = maximumSet($set);
print "<pre>";
print_r($x);
print "</pre>";