网站开发业务需求分析,专业网站设计公司和普通设计公司的区别,建设工程施工合同在哪个网站,渠道推广费用咨询题目描述 给定n个开区间#xff0c;从中选择尽可能多的开区间#xff0c;使得这些开区间两两没有交集。 输入描述 输出描述 输出一个整数#xff0c;表示最多选择的开区间个数。 样例1输入 4 1 3 2 4 3 5 6 7 输出 3 解释 最多选择(1,3)、(3,5)、(6,7)三个区间#xff0c;它…题目描述 给定n个开区间从中选择尽可能多的开区间使得这些开区间两两没有交集。 输入描述 输出描述 输出一个整数表示最多选择的开区间个数。 样例1输入 4 1 3 2 4 3 5 6 7 输出 3 解释 最多选择(1,3)、(3,5)、(6,7)三个区间它们互相没有交集。 #includebits/stdc.h
using namespace std;
const int MAXN 100;
int a[MAXN];
struct qj{int x;//左端点int y;//右端点
};//定义区间结构体依次输入区间的左右端点
bool cmp(qj a, qj b){//qj类型的a和breturn a.y b.y;//返回右端点较小的区间
}
int main(){struct qj a[MAXN];int n;cin n;for(int i0;in;i){scanf(%d %d,a[i].x,a[i].y);}sort(a,an,cmp);//按照右端点小的顺序int last a[0].y;//第一个区间的左端点int count 1;//第一个区间一定能被选中for(int i1;in;i){//从第二个区间开始判断if(a[i].x last){//如果当前区间的左端点大于等于上一个区间的右端点count;//则不会交集个数加1last a[i].y;//更新当前的右端点}}printf(%d,count);return 0;
}
