问题描述：设有n个活动的集合E = {1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si < fi 。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当si >= fj或sj >= fi时，活动i与活动j相容。选择出由互相兼容的活动组成的最大集合。
输入格式
第一行一个整数 n；
接下来的 n行，每行两个整数 si和 fi。
输出格式
输出互相兼容的最大活动个数。
样例
样例输入
样例输出
2
数据范围与提示
1≤n≤1000
其实这种题只要将末尾时间从小到大排序即可，证法请读者自己思考
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
int f=1,ans=0;char c;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
struct node{
int f,e;
}a[1001];
bool cmp(node a,node b)
{
return a.e=t) ans++,t=a[i].e;
cout<
种树 https://loj.ac/problem/10001
题目描述
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民想在门前种些树并指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量。
写一个程序完成以下工作：
输入输出格式
输入格式：
第一行包含数据N，区域的个数(0
第二行包含H，房子的数目(0
下面的H行描述居民们的需要：B E T，0
输出格式：
输出文件只有一行写有树的数目
输入输出样例
输入样例#1：
9
4
1 4 2
4 6 2
8 9 2
3 5 2
输出样例#1：
5
从最后从小到大排序，使用used数组记录当前位置有没有树即可
#include
#include
#include
#include
#include
using namespace std;
inline int read()
{
int f=1,ans=0;char c;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
return ans*f;
}
struct node{
int f;int e;int x;
}a[50001];
bool used[30001];
bool cmp(node a,node b)
{
return a.e=a[i].f;j--)
if(used[j]) ans++;
if(ans>=a[i].x) continue;
for(int j=a[i].e;j>=a[i].f;j--)
{
if(!used[j]) used[j]=1,ans++;
if(ans==a[i].x) break;
}
}
int sum=0;
for(int i=1;i<=n;i++)
if(used[i]) sum++;
cout<