P1791 线段覆盖
题目描述
已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。
输入输出格式
输入格式：
第一行为一整数N。接下来有N行，每行包含两个整数 (Ai 和 Bi), 用空格隔开。
输出格式：
整数p，即删除后余下的线段数。
输入输出样例
输入样例#1：
3
6 3
1 3
2 5 输出样例#1：
2 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<algorithm>
5 using namespace std;
6 struct node
7 {
8 int x;
9 int y;
10 }a[10001];
11 int comp(const node & a , const node & b)
12 {
13 return a.y<b.y;
14 }
15 int main()
16 {
17 int n;
18 scanf("%d",&n);
19 for(int i=1;i<=n;i++)
20 {
21 scanf("%d%d",&a[i].x,&a[i].y);
22 if(a[i].x>a[i].y)
23 swap(a[i].x,a[i].y);
24 }
25
26 sort(a+1,a+n+1,comp);
27 int last=-10000;
28 int ans=0;
29 for(int i=1;i<=n;i++)
30 {
31 if(a[i].x>=last)
32 {
33 ans++;
34 last=a[i].y;
35 }
36 }
37 printf("%d",ans);
38 return 0;
39 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-05-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录