贪心算法详解（第二部分）

本文主要是介绍贪心算法详解（第二部分），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二、区间覆盖问题

算法讲解：

给定了一个长度为n的区间，再给出m条线段的左端点和右端点，问最少使用多少条线段可以将整个区间覆盖？贪心的思路就是尽量找出更长的线段。一般是这样的解题步骤：
一、把每个线段按照左端点升序排序
二、假设已经覆盖的区间是[left，right]，在剩下的线段种找出所有左端点小于等于right且右端点最大的线段，把这个线段加入到已经覆盖了的区间上，更新完成覆盖的区间。然后不断重复这个操作。

我知道你们肯定想看小哥哥是如何去实现这个算法的，写个图示给你们看：

例题1：POJ 1089 Intervals

题目大意：

这题我觉得可能是外国人出的，这英语翻译出来真心没看懂啥意思，直到我看到了样例才明白意思。
这题的意思是，给出n组线段，让这些线段可以合并的去合并，问合并完之后，剩下的线段是哪些。

算法分析：

区间如果可以合并，说明他们有覆盖的部分，我们就当作区间覆盖去处理：
先对每个线段的起点进行排序，然后维护一个当前已经完成的区间[left，right]
然后开始遍历，如果发现right < a[i].left那么就说明这个地方不能连接上，需要断开，所有前面已经维护的区间就是一个不可并的区间，此时再换到下一个需要维护的区间。如果发现a[i].right > right说明发现了一个可并的并且能延长可并区间的线段，此时要做的事情就是更新right也就是更新最长区间。

AC代码如下：

#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 5e4 + 5;
int n, pos;
struct Node{
	int sta, en;
}a[maxn];
bool cmp(Node n1, Node n2){
	return n1.sta < n2.sta;
}
int main(){
	cin >> n;
	for(int i = 0;i < n;i++)
		cin >> a[i].sta >> a[i].en;
	sort(a, a + n, cmp);
	int l = a[0].sta, r = a[0].en;
	for(int i = 1;i < n;i++){
		if(r < a[i].sta){
			cout << l << ' ' << r << endl;
			l = a[i].sta;
			r = a[i].en;
		}else if(a[i].en > r)
			r = a[i].en;
	}
	cout << l << ' ' << r << endl;
	return 0;
} 

写在最后：区间贪心的问题大概就是这些，博主也要去再做些题去扩充关于区间贪心的题量，然后后期有新的发现了再去更新关于它的博客吧。

这篇关于贪心算法详解（第二部分）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！