贪心算法模型2-区间型

（一）选择不相交区间

数轴上有n个开区间，尽量选多的没有公共点的区间

【解法】先排序(b从小到大，b相等时a从大到小)，然后按顺序遍历一遍选择不相交区间

#include <iostream> #include <algorithm> using namespace std; struct Interval { //闭区间[a,b] int a, b; }; Interval c[2100]; int n, t, k; bool cmp(const Interval I1, const Interval I2) { if(I1.b > I2.b) return false; if(I1.b < I2.b) return true;// 先根据右端从小到大排序 return I1.a > I2.a; //右端相等 区间短的在前 } int main() { cin >> n; for(int i=0; i<n; i++) cin >> c[i].a >> c[i].b; sort(c, c+n, cmp); for(int i=0; i<n; i++) { if(c[i].a > t) { //t是上个区间的右端;a>t说明不与上个区间相交 k ++; t = c[i].b; } } cout << k << endl; return 0; }

（二）区间选点

数轴上有n个闭区间，取尽量少的点，使每个区间至少有一个点

【解法】

先排序(b从小到大，b相等时a从大到小，与上面的排序一样)，

然后每次选择第一个区间最后一个点，往下找到包含此点的区间，又找到第一个 不包含此点的区间，选择

#include <iostream> #include <algorithm> using namespace std; struct Interval { int a, b; }; Interval q[10001]; int n, sn, num; //sn表示多少个区间已经包含一个点 bool flag[10001]; //区间i是否已经包含了一个点 bool cmp(const Interval I1, const Interval I2) { if(I1.b > I2.b) return false; if(I1.b < I2.b) return true; return I1.a > I2.a; } int main() { cin >> n; for(int i=0; i<n; i++) cin >> q[i].a >> q[i].b; sort(q, q+n, cmp); for(int i=0; i<n; i++) { if(flag[i]) continue; num ++; sn ++; flag[i] = true; if(sn == n) break; for(int j=i+1; j<n; j++) if(!flag[j] && q[i].b >= q[j].a && q[i].b <= q[j].b) { flag[j] = true; sn ++; if(sn == n) break; } } cout << num << endl; return 0; }

（三）区间覆盖

更新ing...