1 条题解

  • 0
    @ 2026-2-1 16:07:56
    #include<bits/stdc++.h>
    using namespace std;
    
    // 存储活动信息:l-活动开始时间,r-活动结束时间
    struct node{
        int l,r;
    }arr[500000]; 
    
    // 比较函数:按活动结束时间r升序排序,r相同时按开始时间l升序
    // 贪心策略:优先选择结束时间最早的活动,以留出更多时间给后续活动
    bool cmp(node x,node y){
        if(x.r == y.r) 
            return x.l < y.l;
        else 
            return x.r < y.r;
    }
    
    int main(){
        long long n;
        cin >> n; // [1] 输入活动总数n
        // [2] 输入每个活动的开始时间和结束时间
        for(long long i = 0; i < n; i++){
            cin >> arr[i].l >> arr[i].r;
        }
        
        sort(arr, arr + n, cmp); // [3] 按结束时间升序排序活动
        
        long long sum = 1; // 记录最多可安排的活动数,初始选第一个活动
        long long sj = arr[0].r; // 记录当前最后一个活动的结束时间
        
        // [4] 贪心选择后续活动:只选开始时间不早于上一个活动结束时间的活动
        for(long long i = 1; i < n; i++){ 
            if(arr[i].l >= sj){ // 当前活动开始时间不冲突
                sum++;
                sj = arr[i].r; // 更新最后一个活动的结束时间
            } 
        }
        cout << sum; // [5] 输出最多可安排的活动数
        return 0;	
    }
    
    • 1

    信息

    ID
    1036
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    6
    已通过
    1
    上传者