首页 > 学院 > 开发设计 > 正文

1214 线段覆盖

2019-11-08 20:04:22

字体：大中小

来源：转载

供稿：网友

题目描述

给定x轴上的N（0<N<100）条线段，每个线段由它的二个端点a_I和b_I确定，I=1,2,……N.这些坐标都是区间（－999，999）的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

输入描述

输入第一行是一个整数N。接下来有N行，每行有二个空格隔开的整数，表示一条线段的二个端点的坐标。

输出描述

输出第一行是一个整数表示最多剩下的线段数。

样例输入

3

6 3

1 3

2 5

样例输出

2

数据范围及提示

0

分析

贪心，按照右端点最小的来。

代码

#include<algorithm>#include<stdio.h>using namespace std;struct seg{ int l,r;}a[105];bool cmp(seg a,seg b){ return a.r<b.r;}int main(){ int n,ans=1,mr,x,y; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); a[i].l=min(x,y); a[i].r=max(x,y); } sort(a+1,a+n+1,cmp); mr=a[1].r; for(int i=1;i<=n;i++) { if(a[i].l>=mr) { mr=a[i].r; ans++; } } PRintf("%d/n",ans); return 0; }

上一篇：确认运行的jdk版本

下一篇：默认构建器 this关键字

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注

新闻热点

荣耀总裁赵明乌镇演讲：荣耀首款5G手机V30下月发布

2019-10-23 09:17:05

搜狐张朝阳：回归媒体是搜狐重新崛起的关键

2019-10-21 09:20:02

华为轮值董事长郭平：虚拟技术创造现实价值

2019-10-21 09:00:12

滴滴英文服务上线两周年用户已超200万

2019-09-26 08:57:12

华为推出全球至快AI训练集群Atlas900

2019-09-25 08:46:36

马斯克：特斯拉正组建中国技术团队

2019-09-25 08:15:43

疑难解答

图片精选

网友关注