首页 > 代码库 > codevs1214 线段覆盖
codevs1214 线段覆盖
题目描述 Description
给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。
输入描述 Input Description
输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。
输出描述 Output Description
输出第一行是一个整数表示最多剩下的线段数。
样例输入 Sample Input
3
6 3
1 3
2 5
样例输出 Sample Output
2
数据范围及提示 Data Size & Hint
0<N<100
#include<iostream>#include<cstdio>#include<algorithm>using namespace std;struct line{ int l; int r;};bool cmp(line a,line b){ return a.r < b.r;}int main(){ int n,dp=1,rpt; line orz[200]; cin>>n; int u,v; for(int i = 1;i <= n;i++){ scanf("%d%d",&u,&v); orz[i].l = u < v ? u : v; orz[i].r = v > u ? v : u; } sort(orz+1,orz+1+n,cmp); rpt = orz[1].r; for(int i = 2;i <= n;i++){ if(orz[i].l >= rpt){ dp++; rpt = orz[i].r; } } cout<<dp<<endl; return 0;}
codevs1214 线段覆盖
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。