AcWing 908. 最大不相交区间数量
给定N个闭区间[ai,bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
输出可选取区间的最大数量。
输入格式
第一行包含整数N，表示区间数。
接下来N 行，每行包含两个整数ai,bi，表示一个区间的两个端点。
输出格式
输出一个整数，表示可选取区间的最大数量。
数据范围
思路
①将每个区间按右端点从小到大排序
②从前往后依次枚举每个区间 如果当前区间中已经包含点，则直接pass 否则，选择当前区间的右端点
类似排节目 一个节目越早结束 一场晚会就越能表演更多的节目
代码
#include<bits/stdc++.h> using namespace std; const int N = 100010; struct Range { int l, r; }range[N]; bool cmp(struct Range a, struct Range b) { return a.r < b.r; } int main() { int n;cin >> n; for (int i = 0;i < n;++i) { int l, r;scanf("%d%d", &l, &r); range[i] = { l,r }; } sort(range, range + n, cmp); int res = 0, ed = -2e9; for (int i = 0;i < n;++i) { if (range[i].l > ed) { ++res; ed = range[i].r; } } cout << res << endl; return 0; }
