蓝桥吧 线段和点 贪心

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxx = 10010;
 4 struct node{
 5     int s; //start，区间的左端点
 6     int e; //end，区间的右端点 
 7 } p[maxx]; //区间数组 
 8 bool cmp(node n1, node n2) { 
 9     if (n1.s != n2.s) {
10         return n1.s < n2.s;
11     }
12     return n1.e > n2.e;
13 }
14 int a[maxx]; //存储点 
15 int main() {
16     int n, m;
17     cin >> n >> m; 
18     for (int i = 1; i <= n; i++) { //n个点 
19         cin >> a[i];
20     }
21     for (int i = 1; i <= m; i++) { //m个区间 
22         cin >> p[i].s >> p[i].e;
23     }
24     sort(p + 1, p + 1 + m, cmp);
25     int k, i, j, st = 1;
26     for (k = 1; k <= n; k++) { //操作的次数=最少需要的点数 
27         //cout << "-------------------" << k << endl;
28         int _max = -1;
29         for (i = 1; i <= n; i++) { //遍历所有点 
30             //cout << "----------" << i << endl;
31             for (j = st; j <= m; j++) {
32                 if (p[j].s > a[i] || p[j].e < a[i]) {
33                     //cout << "--j:" << j << " break " << endl;
34                     break;
35                 }
36             } 
37             if (j > _max) { //看这个点最多可以满足多少个区间。
38                 _max = j;
39                 //cout << "-_max:" << _max << endl;
40             }
41         }
42         st = _max; //下次开始的时间就在上一次点的地方开始，寻找满足的点
43         //cout << "--st:" << st << endl;
44         if (st == m + 1) { //所有的线段满足了，就直接退出。
45             break;
46         }
47     }
48     if (k == n + 1) {
49         cout << -1 << endl;
50     } else {
51         cout << k << endl;
52     }
53     return 0;
54 }