四大网站是哪四大,餐饮品牌设计项目,照片制作软件免费,兴化市建设局网站题目
给定 N 个闭区间 [ai,bi]#xff0c;请你在数轴上选择若干区间#xff0c;使得选中的区间之间互不相交#xff08;包括端点#xff09;。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N#xff0c;表示区间数。
接下来 N 行#xff0c;每行包含两个整…题目
给定 N 个闭区间 [ai,bi]请你在数轴上选择若干区间使得选中的区间之间互不相交包括端点。
输出可选取区间的最大数量。
输入格式
第一行包含整数 N表示区间数。
接下来 N 行每行包含两个整数 ai,bi表示一个区间的两个端点。
输出格式
输出一个整数表示可选取区间的最大数量。
数据范围
1≤N≤10^5, −10^9≤ai≤bi≤10^9
输入样例
3
-1 1
2 4
3 5输出样例
2
题解
#include iostream
#include algorithm
using namespace std;
const int N 100010;
//区间数量
int n;
//区间结构体
struct Range{int l, r;bool operator (const Range W)const{return r W.r;}
}range[N];int main(){cin n;for (int i 0; i n; i ){cin range[i].l range[i].r;}//按照右端点进行排序sort(range, range n);//res存储最大不相交区间数ed表示设定的左端点比较值int res 0, ed -2e9;for (int i 0; i n; i )//如果左端点大于设定值if (ed range[i].l){//不相交区间数量1res ;//设定值为右端点值ed range[i].r;}cout res endl;return 0;
}
