当前位置：首页 > news >正文

贪心-区间问题——acwing

news 来源：原创 2025/7/5 0:53:28

题目一：最大不相交区间数量

908. 最大不相交区间数量 - AcWing题库

分析

跟区间选点一样。区间选点：贪心——acwing-CSDN博客

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;struct Range {int l, r;// 重载函数bool operator < (const Range &W) const {return r < W.r;}
} range[N];int main() {int n;cin >> n;for(int i = 0; i < n; i ++) {int l, r;cin >> l >> r;range[i] = {l,r};}// sort右端点 // range里边有重载函数定义sort(range, range + n);// 选点每次选 右端点，因为按右端点排序，可以可以尽可能覆盖多个区间，// 选右端点就是局部最优的体现int res = 0, end = -2e9;// 枚举区间 一一判断选点（已覆盖直接pass，没覆盖则更新，选局部最优解点）for(int i = 0; i < n; i ++) {//当前左区间 选点值if(range[i].l > end) {res ++; // 选点＋1end = range[i].r; //更新为当前右区间}}cout << res << endl;return 0;
}

题目二：区间分组

906. 区间分组 - AcWing题库

分析

首先用一个二维数组将区间左右端点存起来。这是数据的存储结构

对左端点排序。

贪心：

每次取所有集合中最小的右端点 与当前区间左端点比较，如果左端点小于说明可以放入结合，也就是更新该集合的右端点。否则，多一个集合，直接入堆。

用小根堆来维护所有集合，因为贪心每次取最小，所以用小根堆维护所有结合的最右端点。

其实就是两个思考，

一是如何存储区间
二是如何解决问题

核心问题通过贪心来解决，按左端点排序

因为涉及最值，用小根堆来存储集合，维护集合。每个集合只需要存储每个集合的有端点。每次都用最小的来比较，这样可以更区间分组更密集，同时如果最小的都不行，那更大的也不行，会有交集，就需要另开集合。

代码

#include<bits/stdc++.h>
using namespace std;vector<vector<int>> a(100010,vector<int> (2,0)); 
int n;int main() {cin >> n;for(int i = 0; i < n; i ++) {int l, r;cin >> l >> r;a[i][0] = l, a[i][1] = r;}sort(a.begin(),a.begin()+n); // 最左端点排序// 小根堆，存所有集合的右端点，集合大小就是priority_queue<int,vector<int>,greater<int>> s;//遍历区间for(int i = 0; i < n; i ++) {//集合中 最小 右端点 都比 左端点； 入队多一个集合if(s.empty() || s.top() >= a[i][0]) s.push(a[i][1]);else { // 当前左端点大，更新最小右端点s.pop();s.push(a[i][1]);}}// 因为用小根堆，存储每一个集合的最后区间右端点，故右端点个数也是集合个数也是组数。cout << s.size() << endl;return 0;
}

题目三：区间覆盖

907. 区间覆盖 - AcWing题库

分析

考虑，区间存储结构，排序左端点，可以使用二维数组，排序右端点可以考虑结构体，加个重载<

解决核心问题：从存储的区间里挑选尽可能少的区间来覆盖一段区间。那么首先左端点需要比该区间左端点<=才能做到覆盖。如果不行，就无解。然后还要在众多左端点比该区间左端点区间小的区间，使得该区间尽可能被覆盖多点（贪心思想体现）。即选右端点最大的，选完，待覆盖区间左端点为被选区间右端点，因为被覆盖了。重复挑选上述步骤，直至使得区间被覆盖，（能覆盖）或者区间遍历完，但仍为未覆盖。也就是无解。

综上所述：

两个边界点。第一个是待覆盖区间左端点，如果所能选区间里没有能覆盖的，（r < st) 那么无解。

第二个边界点。如果待覆盖区间被覆盖完（r>=ed)问题解决。或者，区间遍历完，仍不能使得完全被覆盖，则无解。

代码

也可以用结构体弄个重载函数来实现区间存储和sort

#include<bits/stdc++.h>
using namespace std;const int N = 1e5+10;
// 二位数组存储区间
vector<vector<int>> a(N,vector<int>(2,0));int main() {int st, ed;cin >> st >> ed;int n;cin >> n;for(int i = 0; i < n; i ++) {int l, r;cin >> l >> r;a[i][0] = l, a[i][1] = r;}//对左端点排序sort(a.begin(),a.begin()+n);int flag = 0, cnt = 0;for(int i = 0; i < n; i ++) {// 贪心：找<=要覆盖区间左端点，右端点覆盖能最大化的int j = i, r = -2e9;while(j < n && a[j][0]<=st) {r = max(r,a[j][1]);j ++;}// 覆盖不下去了，判断左边界if(r<st) {break;}// 找到一个区间覆盖一次。cnt ++;//判断 右边界if(r >= ed) {flag = 1;break;}//区间收缩st = r;i = j-1; // i结束循环会自增}if(flag) cout << cnt << endl;else cout << -1 << endl;return 0;
}

题目一：最大不相交区间数量

分析

代码

题目二：区间分组

分析

代码

题目三：区间覆盖

分析

代码

相关文章：