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

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

具体算法步骤如下：

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即为最优解。