分析

首先这儿有一道思想比较类似的题
P1250 种树
都是比较简单的贪心
但具体的情况是不一样的
我们发现，对于这个用户，所有可以覆盖他的段为
那么我们按照为双关键字排序之后
贪心得选取第一个可以继续放的区间
一定是不会使结果劣
时间复杂度：

代码

//
#include <algorithm>
#include <queue>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(int i=A;i<=B;i++)
#define BOR(i,A,B) for(int i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define Skip cout<<endl;
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const int MaxN=1e4+10;

struct Node { 
    int From,To,Limit; 
}Line[MaxN];

inline bool Comp_one(Node A,Node B) { if(A.From!=B.From) return A.From<B.From; else return A.To<B.To; }
struct Comp_two {
    bool operator () (Node A,Node B)const
    { return A.To>B.To; } 
};
// inline bool Comp_two(Node A,Node B) { return A.To>B.To; }

int Total,Test;
priority_queue<Node,vector<Node>,Comp_two>Temp;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

int main() {
    // File();
    // ios::sync_with_stdio(false);
    while(scanf("%d %d",&Total,&Test)!=EOF) {
        FOR(i,1,Test) scanf("%d %d %d",&Line[i].From,&Line[i].To,&Line[i].Limit);
        while(!Temp.empty()) Temp.pop();
        sort(Line+1,Line+Test+1,Comp_one);
        // FOR(i,1,Test) { cout<<Line[i].From<<" "<<Line[i].To<<" "<<Line[i].Limit<<endl; }
        int Loc=1,Ans=0;
        FOR(i,1,Total) {
            while(!Temp.empty() && Temp.top().To<i) { Temp.pop(); }
            while(Loc<=Test && Line[Loc].From==i) { Temp.push(Line[Loc++]); }
            if(!Temp.empty()) {
                Node New=Temp.top();
                Temp.pop();
                Ans++; New.Limit--;
                if(New.Limit) Temp.push(New);
            }
        }
        printf("%d\n",Ans);
    }
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}