Peter算法小课堂—区间模型

本文主要是介绍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;
}