Peter算法小课堂—区间模型

Peter Pan来啦……

最大不重叠区间数

二话不说，先来一道题

大家想想怎么贪心？我们可以将每一个美食摊位抽象成一个区间，区间左端点为开始排队时间，右端点为结束排队时间。其中，时间信息可以用数轴表示。

额……我们先给出一个错误的贪心

大家想想有没有反例？我将这种反例称之为“锁结构”，如下图

按照上面的贪心法，我们应该选粉色的时间段，但是呢？我们能找到更优的选法，即两端红色的时间段。那么，正确的贪心怎么做的呢？

我们来个证明：我们要最多的不重叠，我们就要腾出时间留给后面的任务，换句话说就要前面的任务早点结束，于是QED。大家尝试做一做。

#include <bits/stdc++.h>
using namespace std;
const int N=109;
int n,x,i,ans;
struct food{
	int s,t;
};
bool cmp(const food& a,const food& b){
	return a.t<b.t;
}
food d[N];
int main(){
	cin>>n;
	for(i=0;i<n;i++) cin>>d[i].s;
	for(i=0;i<n;i++) cin>>d[i].t;
	sort(d,d+n,cmp);
	x=-1;ans=0;
	for(i=0;i<n;i++)
		if(d[i].s>=x){
			ans++;
			x=d[i].t;
		}
	cout<<ans<<endl;
	return 0;
}

不重叠区间最少分组数

看着标题好像有点难懂，来道题吧

我们依然可以把每门课抽象成一个区间

这个贪心有点难，证明也很奇怪，所以，我打成图。

具体证明见后。

证明

浅谈信息学竞赛中的区间问题.docx-综合论文-在线文档投稿赚钱网 (book118.com)

结束啦