贪心、排序

将给出区间按右端点从小到大排序并遍历，对于每个区间贪心在其最靠右的空位种树。由于区间左侧的其他区间已经全部处理完成，在当前区间最靠右的空位种树对其他未被处理的区间的贡献最大。

时间复杂度 $O(nm)$，其中 $1 \leq n \leq 3 \times 10^4$，$1 \leq m \leq 5 \times 10^3$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r,w;}s[5005];
int n,m,ans,w[30005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&s[i].l,&s[i].r,&s[i].w);
    sort(s+1,s+m+1,[](auto x,auto y){return x.r<y.r;});
    for(int i=1;i<=m;i++){
        int l=s[i].l,r=s[i].r,res=s[i].w;
        for(int j=l;j<=r;j++) res-=w[j];
        for(int j=r;j>=l;j--){
            if(res<=0) break;
            if(w[j]==0) --res,w[j]=1;
        }
    }
    for(int i=1;i<=n;i++) ans+=w[i];
    printf("%d\n",ans);
    return 0;
}