首页 > 代码库 > 区间型贪心总结（1）

区间型贪心总结（1）

2024-08-24 23:10:16   217人阅读

1.选择不相交区间。数轴上有n个开区间（ai,bi)。尽量选择多个区间，使得这些区间两两没有公共点。

     a.对区间进行排序，排序成b1<=b2<=b3<=.....的形式

　  b.第一个区间一定要选！

　  c.

          Case 1: a1 > a2　　　　这种情况下选择1区间

          Case 2: 排除Case 1后，一定有a1<=a2<=a3<=....., 此种情况应该选1区间，因为此时最优

题目：1214（CODEVS）

下面给出源码

 

 1 //洛谷1214 线段覆盖
 2 //区间型贪心 
 3 
 4 #include<iostream>
 5 #include<algorithm>
 6 using namespace std;
 7 struct phase {
 8     int right, left;
 9 };
10 bool compare(phase a, phase b) {
11     return a.left <= b.left ;
12 }
13 int main() {
14     int n;
15     cin >> n;
16     phase *a = new phase[n];
17 
18     for(int i = 0; i < n; i++) {
19         int r, l;
20         cin >> r >> l;
21         a[i].right = r <= l ? r : l;
22         a[i].left = r > l ? r : l;
23     }
24 
25     sort(a, a + n, compare);
26     int ans = 0;
27     int x = a[0].left ;
28 
29     for(int i = 1 ; i < n; i++) {
30         if(a[i].right >= x) {
31             ans++, x = a[i].left;
32         }
33     }
34 
35     cout << ans + 1 << endl;
36     return 0;
37 
38 }

 

区间型贪心总结（1）


联系
我们