贪心算法 区间覆盖问题

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。而区间覆盖问题是指给定一些区间，选出最少的点，使得每个区间都至少有一个点被选中。这个问题可以使用贪心算法来解决。具体来说，可以按照区间的右端点从小到大排序，然后从左到右遍历每个区间，如果当前点不在前一个区间的右端点之后，则需要增加一个点。这样可以保证选出的点数最少。

相关问题

贪心算法区间覆盖代码

下面是使用贪心算法解决区间覆盖问题的代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int s, t, n;

struct num {
    int begin;
    int end;
    bool operator< (const num &w) const {
        return begin < w.begin;
    }
} p[N];

int main() {
    cin >> s >> t;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        p[i = {a, b};
    }
    
    sort(p, p + n);
    
    int res = 0;
    bool k = false;
    
    for(int i = 0; i < n; i++) {
        int j = i, r = -2e9;

        while(j < n && p[j].begin <= s) {
            r = max(p[j].end, r);
            j++;
        }
        
        if(r < s) {
            res = -1;
            break;
        }
        
        res++;
        
        if(r >= t) {
            k = true;
            break;
        }
        
        s = r;
        i = j - 1;
    }
    
    if(!k) {
        res = -1;
    }
    
    cout << res << endl;
    
    return 0;
}

该代码实现了贪心算法来解决区间覆盖问题。首先，根据输入的s和t，以及n个区间的起始和结束点，将区间按照起始点从小到大进行排序。然后，对每个区间进行遍历，找到能够覆盖起始点s的区间，并更新s为该区间的结束点。如果没有找到能够覆盖起始点s的区间，则将结果res设为-1。最后，输出结果res。

贪心算法解决区间覆盖问题

区间覆盖问题是指在一条数轴上，给定若干个区间，选取尽可能少的区间，使得这些区间能够覆盖整个数轴。贪心算法是一种自下而上的贪心策略，每次选择能够覆盖尽可能多未被覆盖区域的区间加入解集合中。

具体算法步骤如下：

1. 将所有区间按照右端点从小到大排序。
2. 初始化当前右端点为负无穷。
3. 遍历所有区间，对于每个区间：
a. 如果当前右端点小于等于该区间的左端点，将该区间加入解集合中，更新当前右端点为该区间的右端点。
4. 返回解集合。

算法时间复杂度为O(nlogn)，其中n为区间个数。以下是Python实现：

def interval_cover(intervals):
    intervals.sort(key=lambda x: x[1]) # 按右端点排序
    right = float('-inf') # 初始化当前右端点
    chosen = [] # 解集合
    for interval in intervals:
        if right <= interval[0]: # 如果当前右端点小于等于该区间的左端点
            chosen.append(interval) # 将该区间加入解集合中
            right = interval[1] # 更新当前右端点为该区间的右端点
    return chosen

其中，intervals是一个包含区间左右端点的列表，如[(1, 3), (2, 4), (3, 5), (4, 6)]。函数返回一个解集合，如[(1, 3), (3, 5), (4, 6)]，它们能够覆盖整个数轴。

该算法的正确性可以通过反证法证明。假设存在一个更优的解集合S'，但该解集合与算法得到的解集合S不同，也就是说它们至少有一个区间不同。我们可以假设在S中覆盖最左边的未被覆盖区域时选择了一个区间I1，而在S'中覆盖同一区域时选择了另一个区间I2。由于I2的右端点在I1的右端点右侧，所以I2能够覆盖的未被覆盖区域一定比I1小，因此在S中选择I1比选择I2更优。这与假设矛盾，因此S即为最优解。