1 条题解
-
0
#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
- 上传者