Description
某条街被划为 n 条路段，这 n 条路段依次编号为 1…n。每个路段最多可以种一棵树。现在居民们给出了 h 组建议，每组建议包含三个整数 b,e,t 表示居民希望在路段 b 到 e之间至少要种 t 棵树。这些建议所给路段的区间可以交叉。请问：如果要满足所有居民的建议，至少要种多少棵树。
Input
第一行为 n，表示路段数。第二行为 h，表示建议数。 下面 h 行描述一条建议：b,e,t 用一个空格分隔。
Output
输出只有一个数，为满足所有居民的建议，所需要种树的最少数量。
Sample Input
9
4
1 4 2
4 6 2
8 9 2
3 5 2
Sample Output
5
思路
以样例为例，首先按右端点升序排序：
要使种的树数目最少，实际是要使树尽可能的种在路段重复地段。类似于安排时间表的问题，用贪心算法处理。排好序后按照路段顺序遍历，并且每次从最右端点向左遍历该路段，即从最右端开始种树。这样可以实现最大限度的把树优先种在重复路段。
以此思路则种树顺序应如图所示：
代码
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
int b, e, t;
}sugg[5001];//suggestion
bool cmp(node x, node y){
return x.e<y.e;//以右端点作为排序标准 升序
}
int main()
{
int b,e,t;
int n,h;
cin>>n>>h;
for(int i=1;i<=h;i++){
cin>>sugg[i].b>>sugg[i].e>>sugg[i].t;
}
sort(sugg+1,sugg+1+h,cmp);
int res=0;
int road[10000]={0};//记录整个道路种树情况
for(int i=1;i<=h;i++){
//先循环遍历此路段是否满足建议需求
for(int j=sugg[i].e;j>=sugg[i].b;j--){//从靠近右端点的地方开始种树
if(road[j]==1){
sugg[i].t--;
}
}
//再循环从右端点开始种树
for(int j=sugg[i].e;j>=sugg[i].b;j--){
if(sugg[i].t==0){//此条建议已被满足
break;
}
if(road[j]==1){//此处已有树
sugg[i].t--;
}else{
sugg[i].t--;
road[j]=1;//种上树
res++;
}
}
}
cout<<res;
}