求覆盖目标区间的最小成本区间集合最优算法方案咨询

你的问题属于加权区间覆盖问题，普通贪心算法（比如每次选覆盖当前位置最远的区间）只适用于无权重（所有区间成本相同）的场景，在带成本的情况下会失效——比如高成本的大区间可能不如多个低成本小区间的组合划算，这也是你遇到困难的核心原因。正确解法是使用动态规划，以下是具体思路和C++实现：

核心思路 #

1. 预处理与排序：过滤掉无法对目标区间产生覆盖贡献的无效区间，将有效区间按右端点升序排列。
2. 离散化端点：收集所有涉及的端点（目标区间端点、所有有效区间的左右端点）并去重排序，将连续数值端点映射到数组索引，降低DP数组的空间复杂度。
3. 动态规划计算：定义dp[i]表示覆盖到第i个离散端点时的最小成本。遍历每个有效区间，找到所有能衔接该区间左端点的已覆盖位置，更新覆盖到该区间右端点的最小成本。
4. 前缀最小值优化：维护前缀最小值数组，快速找到衔接区间左端点的最小成本，避免暴力遍历提升效率。

C++ 实现代码 #

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <climits>

using namespace std;

struct Interval {
    int l, r, cost;
    bool operator<(const Interval& other) const {
        return r < other.r; // 按右端点升序排序
    }
};

int main() {
    // 示例输入：目标区间[20,100]，次级区间及成本
    vector<Interval> intervals = {
        {20, 45, 10},
        {30, 75, 20},
        {70, 85, 5},
        {80, 100, 15},
        {20, 100, 60} // 高成本全覆盖区间，用于验证最优解
    };
    int target_start = 20, target_end = 100;

    // 过滤无效区间：去掉完全在目标区间外的区间
    vector<Interval> valid_intervals;
    for (auto& inter : intervals) {
        if (inter.r <= target_start || inter.l >= target_end) {
            continue;
        }
        // 调整区间至目标范围内，减少不必要计算
        inter.l = max(inter.l, target_start);
        inter.r = min(inter.r, target_end);
        valid_intervals.push_back(inter);
    }

    // 按右端点升序排序
    sort(valid_intervals.begin(), valid_intervals.end());

    // 离散化所有端点
    vector<int> points;
    points.push_back(target_start);
    points.push_back(target_end);
    for (auto& inter : valid_intervals) {
        points.push_back(inter.l);
        points.push_back(inter.r);
    }
    sort(points.begin(), points.end());
    // 去重
    auto last = unique(points.begin(), points.end());
    points.erase(last, points.end());

    // 建立端点到数组索引的映射
    unordered_map<int, int> point_idx;
    for (int i = 0; i < points.size(); ++i) {
        point_idx[points[i]] = i;
    }

    int n = points.size();
    vector<int> dp(n, INT_MAX);
    // 初始状态：覆盖到目标左端点的成本为0
    dp[point_idx[target_start]] = 0;

    // 维护前缀最小值数组，快速获取衔接左端点的最小成本
    vector<int> prefix_min(n, INT_MAX);
    prefix_min[0] = dp[0];
    for (int i = 1; i < n; ++i) {
        prefix_min[i] = min(prefix_min[i-1], dp[i]);
    }

    for (auto& inter : valid_intervals) {
        int l_idx = point_idx[inter.l];
        int r_idx = point_idx[inter.r];

        // 获取能衔接当前区间左端点的最小成本
        int prev_min_cost = prefix_min[l_idx];
        if (prev_min_cost != INT_MAX) {
            if (dp[r_idx] > prev_min_cost + inter.cost) {
                dp[r_idx] = prev_min_cost + inter.cost;
                // 更新前缀最小值数组，确保后续计算能拿到最新的最小成本
                for (int i = r_idx; i < n; ++i) {
                    prefix_min[i] = min(prefix_min[i], dp[r_idx]);
                }
            }
        }
    }

    int result = dp[point_idx[target_end]];
    if (result == INT_MAX) {
        cout << "无法覆盖目标区间" << endl;
    } else {
        cout << "最小总成本：" << result << endl; // 示例输出为50
    }

    return 0;
}

关键细节说明 #

• 无效区间过滤：直接排除右端点小于目标左端点、左端点大于目标右端点的区间，这些区间对覆盖目标无贡献。
• 离散化的必要性：若区间端点范围极大（如到1e9），直接用端点值作为DP数组下标会导致内存溢出，离散化后可将端点映射到有限索引范围。
• 前缀最小值优化：将找前置最小成本的时间复杂度从O(n)降至O(1)，整体算法时间复杂度主要由排序步骤决定，为O(n log n)。

内容的提问来源于stack exchange，提问作者dump34