首先按照路段结束的位置从小到大排序 这样能保证每个路段都被充分利用 要保证所种的树尽可能地少则要尽量让更多 的树种植到公共区域上，这样就能够一箭多雕 以更少的树满足更多的人的需求，但是我们还需要一个数组，来标记每个区域是否被种上了树，如果该区域被种上了，就不需要再重复的去种植了

#include<stdio.h>
#include<stdlib.h>
/*首先按照路段结束的位置从小到大排序
  这样能保证每个路段都被充分利用
  要保证所种的树尽可能地少则要尽量让更多
  的树种植到公共区域上，这样就能够一箭多雕
  以更少的树满足更多的人的需求，但是我们还需要一个数组
  来标记每个区域是否被种上了树，如果该区域被种上了，就不需要再重复
  的去种植了 
*/ 
typedef struct tree{
	int b;
	int e;
	int t;
}Tree;
Tree array[5008];
int used[50000];//标识是否被种植,全局变量默认初始化为0 
int comp(const void *a , const void *b){
	  Tree *c = (Tree *)a;
	  Tree *d = (Tree *)b;
	  return c->e-d->e;
}
int main(){
	int n;//表示总共n段路 
	int h;//表示总共h条建议
	int number = 0;//表示树的数量
	int flag;//标识每个路段应该种植的树的数量，如果flag已经达到该路段需要种植的树的数量则不需要再种植了 
	scanf("%d",&n);//路段数 
	scanf("%d",&h);//建议数 
	for(int i=0; i<h; i++){
		scanf("%d %d %d",&array[i].b,&array[i].e,&array[i].t);
	}
	qsort(array,h,sizeof(array[0]),comp);
	for(int i=0; i<h; i++){
	   flag = 0;//从第一个路段开始从后往前遍历 ，之所以从后往前是因为尽可能多的想树种植在公共区域
	   //查看是否在公共区域已经种植了树了 
	   for(int j=array[i].b; j<=array[i].e; j++){
	   	   if(used[j]){
	   	   	  flag++;
			}
	   }
	   //如果公共区域已经种植了足够的树则不需要再种植了 
	   if(flag >= array[i].t)
	   continue; 
	   for(int j=array[i].e; j>=array[i].b; j--){
	   	   if(!used[j]){//如果该区域没有被种植
	   	      used[j] = 1;//将该区域标记为1表示已经种植了 
			  flag++;//种下一棵树 
	   	   	  number++;//总数加一 
	   	if(flag == array[i].t)//如果种植的数量已经达到该路段的要求则不需要再种植了
		   break;
      }
	} 
  }
  printf("%d",number);
}

这道题必须要能够考虑到公共区域尽可能多的种植树的思想，然后围绕这个想法去展开，因为公共的区域只可能是当前路段的结束位置和上一个路段开始的位置之间的交集，那么从每个路段的结束位置开始种植，就可以尽可能地优先利用到公共区域， 但是一定要标记在哪些路段种植的树木以便下一个路段进行遍历，如果公共区域种植的树木已经足够下一个路段则不再种植下一个路段所需要的树木，如果不够则下一个路段也从后往前便利保证优先利用公共区域直到满足该路段的要求为止。 这就是贪心算法的原理，由子问题的最优解得到最终问题的最优解

P1108. 街上的树

题意概述

有一个长度固定的路段，有多组建议，建议是在某一确定路段上至少要多少棵树，最少要种多少树。

题意分析

这里我们可以想想，要使得总树比较少，就要让尽可能多的重叠区域栽上树。 所以，我们回到贪心算法上来。只需要将路段以结束位置为关键字进行排序，我们得到的这个序列后，以路段结束位置为起点向路段开始方向种树。这样就可以尽可能多的树种在一起。

不过这个地方还要注意一个特判，如果区域内有树，我们就不能重复种树了，所以需要将当前路段内需要种树的范围内已经有的树计算出来。

1. 以路段的结束位置为关键字排序
2. 判断种树区域内已种的树
3. 以结束位置向开始位置补全应该种的树

种树就同时进行计数，最后输出所计数即可

可行代码

#include <iostream>
#include <algorithm>
using namespace std;
struct line {
    int s, e, v;
} a[5005];
int n, m, ans = 0;
bool used[30005] = {0};
bool cmp(line a, line b) { return a.e < b.e; }
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        scanf("%d%d%d", &a[i].s, &a[i].e, &a[i].v);
    sort(a + 1, a + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        int k = 0;
        for (int j = a[i].s; j <= a[i].e; j++)
            if (used[j])
                k++;
        if (k >= a[i].v)
            continue;
        for (int j = a[i].e; j >= a[i].s; j--) {
            if (!used[j]) {
                used[j] = 1;
                k++;
                ans++;
                if (k == a[i].v)
                    break;
            }
        }
    }
    printf("%d", ans);
    return 0;
}

END