六、完善程序-2

给出n个区间,第i个区间的左右端点是[,],现在要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每一个0<=i<=m都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数n和m (1<=n<=5000,1<=m<=10^9)
接下来n行,每行两个整数, (0<=,<=m)。
提示:使用贪心法解决这个问题。先用o(n^2)的时间复杂度排序,然后贪心选择这些区间。
试补全程序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
using namespace std;
const int MAXN=5000;
int n,m;
struct segment{int a,b;}A[MAXN];
void sort(){
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
        if (__1__){
            segment t=A[j];
            __2__
        }
}
int main(){
     cin>>n>>m;
    for (int i = 0; i < n; i++)
        cin>>A[i].a>>A[i].b;
  
     sort();
    int p=1;
    for (int i = 0; i < n; i++)
        if(__3__)
            A[p++]=A[i];
    n=p;
    int ans=0,r=0;
    int q=0;
    while(r<m){
        while(__4__)
            q++;
        __5__;
        ans++;
          }
     cout<<ans<<endl;
    return 0;
}
Scroll to Top