首页 > > 程序设计 > C/C++ >

P1791 线段覆盖

2018-06-17 22:40:32来源：未知阅读 ()

题目描述

已知数轴上0<N<10000条线段。每条线段按照端点Ai和Bi（Ai<>Bi,i=1..N）定义。端点坐标在（-999，999）内，坐标为整数。有些线段可能相交。编程实现删除最少数目的线段，使得余下的任意两条线段不相交。

输入输出格式

输入格式：

第一行为一整数N。接下来有N行，每行包含两个整数 (Ai 和 Bi), 用空格隔开。

输出格式：

整数p，即删除后余下的线段数。

输入输出样例

输入样例#1：

输出样例#1：

 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 }