1214 线段覆盖 非结构体做法
1214 线段覆盖
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 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
贪心解法：首先将线段端点调整为左端点小于（或等于）右端点；第二，根据右端点将线段从小到大排序；第三，扫描一遍，每次遇到的第一个与当前的max不想交的即为最优选择。
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 int a[10001];
5 int b[10001];
6 int main()
7 {
8 int n;
9 cin>>n;
10 for(int i=1;i<=n;i++)
11 {
12 cin>>a[i]>>b[i];
13 a[i]=a[i]+300;
14 b[i]=b[i]+300;
15 if(a[i]>b[i])swap(a[i],b[i]);
16 }
17 for(int i=1;i<=n;i++)
18 {
19 for(int j=1;j<n;j++)
20 {
21 if(b[j]>b[j+1])
22 {
23 swap(b[j],b[j+1]);
24 swap(a[j],a[j+1]);
25 }
26 }
27
28 }
29 int ans=0;
30 int maxn=-1;
31 for(int i=1;i<=n;i++)
32 {
33 if(a[i]>=maxn)
34 {
35 ans++;
36 maxn=b[i];
37 }
38 }
39 cout<<ans;
40 return 0;
41 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-18 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录