Java教程

贪心算法详解(第二部分)

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

二、区间覆盖问题

算法讲解:

给定了一个长度为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;
} 
写在最后:区间贪心的问题大概就是这些,博主也要去再做些题去扩充关于区间贪心的题量,然后后期有新的发现了再去更新关于它的博客吧。
这篇关于贪心算法详解(第二部分)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!