贪心 区间选点AC905

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; struct Range{ int l, r; }h[N]; // 自定义比较函数 bool cmp(Range a, Range b){ return a.r < b.r; // 按右端点从小到大 } int main(){ int n; cin>>n; for(int i=0;i<n;i++){ int l, r; cin>>l>>r; h[i] = {l, r}; } // 使用自定义比较函数排序 sort(h, h+n, cmp); int res=0, end=-2e9; // end表示最后选择的点 for(int i=0;i<n;i++){ // 如果当前区间不包含最后选择的点 if(end < h[i].l){ res++; // 需要新点 end = h[i].r; // 选择当前区间的右端点 } // 否则（end >= h[i].l）说明区间已包含点，跳过 } cout<<res<<endl; return 0; }

这个sort也可以用重载运算符写

struct Range{ int l, r; // 重载小于运算符，按右端点排序 bool operator< (const Range &W) const { return r < W.r; } }h[N]; // 使用lambda表达式排序 sort(h, h+n, [](Range a, Range b){ return a.r < b.r; // 按右端点从小到大 }); // 定义比较仿函数 struct Cmp{ bool operator()(Range a, Range b){ return a.r < b.r; } }; // 使用仿函数排序 sort(h, h+n, Cmp());

关于原题中描述是位于区间端点上的点也算作区间内。

但实际上用end < h[i].l也能AC

1. 如果end == l：点end在区间[l, r]的左端点

   • 根据题目，端点算区间内 ✅

   • 当前区间已包含点end

   • 应该跳过当前区间

排序：[(1,3), (3,5)] i=0: end=-∞ < 1 → true 选择点3, end=3, res=1 i=1: end=3 < 3 → false 跳过区间(3,5) 结果：res=1 ✓

还有vector的写法

#include <iostream> #include <algorithm> #include <vector> using namespace std; const int N = 100010; //保存区间 vector<vector<int>> a(N,vector<int>(2,0)); int n; int main() { cin >> n; //读入区间 for(int i = 0; i< n; i++) { int l, r; cin >> l >> r; a[i][0] = l; a[i][1] = r; } // 按右端点排序 sort(a.begin(), a.begin() + n, [](vector<int> &a, vector<int> &b){return a[1] < b[1];}); // res 保存答案，end 是当前选的点 int res = 0, end = -1e9 - 10; // 遍历区间 for(int i = 0; i < n; i++) { // 如果当前选的点覆盖了该区间，则跳过 if(end >= a[i][0] && end <= a[i][1]) continue; else { // 选的点+1, 选的点更新为区间右端点 res++; end = a[i][1]; } } cout << res; return 0; }