51Nod 2201 做任务一

Problem

B君和m个人一起，要完成n个任务，在这个题中，m个人会看着这B君，自己什么都不做。

第i个任务有一个开始时间s[i]和结束时间e[i]（保证s[i]<=e[i]），一个人完成两个任务的时间区间，不能有交集，但是可以首尾相连。（参考样例）

换句话说，如果一个人依次完成了(s[1], e[1]) (s[2], e[2]) (s[3], e[3])这3个任务，那么这3个任务需要满足s[1]<=e[1]<=s[2]<=e[2]<=s[3]<=e[3]。

同一个任务只能完成一次，并且中间不能换人。

问B君一个人最多可以完成多少个任务。

(单组 n <= 100000)

(所有 n 求和 <= 200000)

(开始时间和结束时间，都是非负整数，且在int范围内。)

(开始时间 <= 结束时间，如果等于的话，意味着这个任务可以瞬间被做完，但是不能没有人做)

Solution

经典贪心，结束时间排序。

Code

#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<string.h>
#include<stack>

#define mem(ss) memset(ss,0,sizeof(ss))
#define fo(d, s, t) for(int d=s;d<=t;d++)
#define fo0(d, s, t) for(int d=s;d>=t;d--)
typedef long long ll;
typedef long double ld;
typedef double db;
const ll mod = 998244353;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

inline int read() {
    int data = 0;
    char ch = 0;
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') data = data * 10 + ch - '0', ch = getchar();
    return data;
}
db fab(db x) {
    return x > 0 ? x : -x;
}
int n,m,T;
struct E{
    int s,t;
}e[100020];
int cmp(E x,E y){
    if(x.t==y.t) return x.s<y.s;
    return x.t<y.t;

}
int main() {
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        fo(i,1,n){
            scanf("%d%d",&e[i].s,&e[i].t);
        }
        sort(e+1,e+1+n,cmp);
        int las=0,ans=0;
        fo(i,1,n){
            if(e[i].s>=las){
                ans++;
                las=e[i].t;
            }

        }
        printf("%d\n",ans);
    }

    return 0;
}