codevs 1214 线段覆盖/1643 线段覆盖 3

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

6 3

1 3

2 5

样例输出 Sample Output

数据范围及提示 Data Size & Hint

0<N<100

1643 线段覆盖 3 数据 n≤100000；

分析：和活动选择差不多，贪心，把线段右节点按递增排列，每次总是选择右节点最小的线段。

两个题的代码一样

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 
 5 struct Seq{
 6     int l,r;
 7     bool operator < (const Seq &a) const 
 8     {
 9         return r < a.r;
10     }
11 }s[1000000];
12 int n,p,last,ans,now=-1e9;
13 int main()
14 {
15     scanf("%d",&n);
16     for (int i=1; i<=n; ++i)
17     {
18         scanf("%d%d",&s[i].l,&s[i].r);
19         if (s[i].l>s[i].r) swap(s[i].l,s[i].r);
20     }
21     sort(s+1,s+n+1);
22     for (int i=1; i<=n; ++i)
23     {
24         if (s[i].l<now) continue;
25         now = s[i].r;
26         ans++;
27     }
28     printf("%d",ans);
29     return 0;
30 }