贪心区间问题

分类
字数统计: 2.9k   |   阅读时长≈ 12 分钟

贪心区间问题

以下例题来自于AcWing 906~908

1. 最大不相交区间数（区间选点）

image-20240307214934220

  • 翻译一下题目吧
    1. 最大不相交区间数：也就是说给定$N$个闭区间，问能从中选出多少个区间使其互不相交（同活动安排问题）
    2. 区间选点：给定 $N$ 个区间，在数轴上选择尽量少的点，使每个区间至少包含一个选出的点（同整数区间问题：找到一个含元素个数最少的集合，使对每一个区间都至少有一个整数属于该集合，输出该集合的元素个数）
    3. 为什么这两个问题其实是同一个问题？观察下方图像，在找不相交区间的时候其实就是把 $N$ 个区间划分成 $M$ 个集合，从这 $M$ 个集合中分别选出一个区间，那么这 $M$ 个集合是一定不相交的，此时 $M$ 就是答案，区间选点中点的个数其实就是集合的个数，只要 $range[i].l>last_r$ 就说明需要新开一个集合了，所以 $ans++$
  • 贪心策略：新建一个结构体存储区间的左端点和右端点，将这$N$个区间按照右端点从小到大排序（因为活动选择越早结束越好），遍历所有的区间，如果当前遍历到的区间左端点的值大于了上一个区间的右端点的值，说明此时区间没有重合，则区间个数$+1$
  • 如果假设选的点都出现在区间的右端点，此时为了让每个区间都至少包含一个交点，就可以作图如下：

image-20240529204230868

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

/*
  解题思路: 活动安排+最大不相交区间+区间选点 
  1) 用一个变量记录上一个区间右端点,把所有区间依据区间右端点从小到大排序
  2) 如果某个区间的左端点＞上一个区间右端点,则选点数+1,或不相交区间的个数+1
  
 */

const int N=1e5+5;

int n;

struct Range {
	int l; 
	int r;
}range[N]; // 每个区间有左右端点

// 按照右端点从小到大排序
bool cmp(Range a,Range b) {
	return a.r<b.r;
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&range[i].l,&range[i].r);	
	}
	
	int res=0;
	int front_r=INT_MIN; // 保证至少有一个集合,即range[i].l一定比初始front_r大 
	sort(range+1,range+1+n,cmp);
    
    // 也可以定义res=1,front_r=(sorted)range[1].r,下面的for循环从i=2开始
	
	for(int i=1;i<=n;i++) {
		if(range[i].l>front_r) {
			front_r=range[i].r; // 更新右端点
			res++; // 点数+1
		}	
	}
	cout<<res;
	return 0;
}

例题：P1250 种树 - 洛谷

  • 题目大意：在区间 $[a,b]$ 内至少种 $c$ 棵树，问树最少的个数
  • 解题思路：
    • 即让尽可能多的树同时在多个区间出现，对每个区间先统计已有树的数量，如果不足 $c$ 棵则补差
    • 为了让树尽可能能被下一个区间用上，补差时应当从末尾补差
    • 因为每个坐标点只能种一棵树，所以还需要一个状态数组 $st$ 辅助存储
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

/*
  解题思路: 
  1) 要在[a,b]种至少c棵树,树最少,即让尽可能多的树同时在多个区间出现,再对多个区间补差
  2) 在补差的时候一定要补在该区间的尾部,因为这样是最后可能让下一个区间用上的
  
 */

const int N=1e5+5;

int n,m,a[N];

struct Range{
	int l;
	int r;
	int n; // 树的个数
}range[N];

bool used[N]; // 判断是否已经有树了(一个点不能种两棵树)

bool cmp(Range a,Range b) {
	return a.r<b.r; // 按右端点从小到大排序
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&range[i].l,&range[i].r,&range[i].n); 	
	}
	sort(range+1,range+1+m,cmp);
	int ans=0;
	for(int i=1;i<=m;i++) {
		int k=0; // 存储该区间内已有的树的个数
		for(int j=range[i].l;j<=range[i].r;j++) if(used[j]) k++;
		// 1) 已满足range[i].n棵树则退出
		if(k>=range[i].n) continue;
		// 2) 不满足,则需要补差,补差需要从末尾补,最有可能给下一个区间用
		for(int j=range[i].r;j>=range[i].l;j--) {
			if(!used[j]) {
				used[j]=true;
				k++;
				ans++; // 树的数量只在此处增加,即所有的树其实都是从末尾补的
				if(k==range[i].n) break; // 已够n棵
			}
		}
	}
	cout<<ans;
	return 0;
}

2. 区间分组

image-20240308190931030

image-20240529205928100

  • 翻译一下题目，现在有$N$个区间，问最少分多少组，能让这些分组中的所有区间两两之间包括端点都没有交集
  • 贪心策略：将所有区间按照左端点从小到大排序，从前往后处理每个区间，判断是否能把这个区间放到现有的某个分组中，即判断 $range[i].l \ > \ 某一分组最大右端点$
    1. 如果存在这样的分组（与某个分组间没有交集），则将区间 $ i $ 放进去，并且更新这个分组的最大右端点（注意，如果与多个分组都有交集则可以放到任意一个分组中，不影响结果，可自行模拟证明）
    2. 如果不存在这样的分组（与每个分组间都有交集），则开一个新组，再把区间 $i$ 放进去
    3. 在判断当前区间是否与某一分组有交集时，只需要与所有分组中最小的分组最大右端点进行比较即可，因为这是最有可能满足 $range[i].l \ > \ 某一分组最大右端点$ 的情况，对于所有分组中最小的分组最大右端点，只需要用一个小根堆来维护即可
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

/*
  解题思路: 
  1) 先将所有区间按照左端点从小到大排序
  2) 用优先队列维护所有分组的整体右端点的最小值,因为在遍历区间时需要用range[i].l与所有分组的max_r比较,而min(max_r)是最容易比range[i].l小的,即最容易插入该分组中
  
 */

const int N=1e5+5;

struct Range {
	int l;
	int r;
}range[N];

bool cmp(Range a,Range b) {
	// 按照左端点从小到大排序
	return a.l<b.l;
}

int main() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		int l,r;
		scanf("%d%d",&l,&r);
		range[i]={l,r};
	}
	
	sort(range+1,range+1+n,cmp);
	// 维护每个分组的最右边界的最小值
	priority_queue<int,vector<int>,greater<int>> pq;
	
	// 枚举区间
	for(int i=1;i<=n;i++) {
		// 如果每个分组的最小的max_r都比当前区间左端点大
		// 说明与每个分组中的区间都要产生交集,则不能放入任何分组
		// 此时新开一个分组
		if(pq.empty() || pq.top()>=range[i].l) {
			pq.push(range[i].r); // 新开分组,保存右端点
		} else {
			// 如果无交集,此时可以放进这个分组中
			// 并维护所有分组中最大右端点的最小值
			pq.pop();
			pq.push(range[i].r);
		}
	}
	// 小根堆的大小就是分组的个数
	cout<<pq.size()<<endl;
	return 0;
}

3. 区间覆盖

image-20240308203244259

image-20240529211220012

  • 翻译一下题目，···，这道题没什么可翻译的
  • 贪心策略：将所有区间按照左端点从小到大排序，从前往后依次枚举每个区间，在所有能覆盖 $start$ 的区间中选择一个右端点最大的区间，然后将 $start$ 更新成为右端点的最大值，继续向后覆盖，如果所有区间都遍历过了但并没有覆盖到 $end$ 的话说明无法完全覆盖，则输出 $-1$
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

/*
  解题思路: 对区间按照左端点从小到大排序,因为每次都要保证覆盖start
  再从满足覆盖start的区间中选出右端点最大的,这样就能保证覆盖线段的区间数最小
  再更新start的值,如果遍历完所有区间能使start>=end,则可覆盖,输出区间数
  
 */

const int N=1e5+5;

struct Range {
	int l;
	int r;
	// 重载运算符
	bool operator<(const Range &W)const {
		return l<W.l;
	}
}range[N];

int main() {
	int st,en;
	cin>>st>>en;
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) {
		int l,r;
		scanf("%d%d",&l,&r);
		range[i]={l,r};
	}
	sort(range+1,range+1+n);
	
	int cnt=0; // 统计区间数
	bool flag=false; // 是否能覆盖完整个区间
	
	// 遍历所有区间
	for(int i=1;i<=n;i++) {
		// front_r:当前覆盖到的区域
		// j:每次从第i个区间后开始找
		int j=i,front_r=INT_MIN;
		while(j<=n && range[j].l<=st) {
			front_r=max(front_r,range[j].r); // 找最大的右端点
			j++;
		}
		// 如果最大的front_r仍小于st,说明线段不可被已有区间覆盖
		if(front_r<st) break;
		// 如果找得到,区间数+1
		cnt++;
		// 已经完全覆盖线段
		if(front_r>=en) {
			flag=true;
			break;
		}
		// 否则更新i和j
		st=front_r; // 迭代st,后面的区间继续和st比
		i=j-1; // 双指针,加速遍历
	}	
	if(!flag) cnt=-1;
	cout<<cnt;
	return 0;
}

4. 区间合并

  • 题目最简单的一集，$N$ 个区间，端点重叠也可合并，求合并后的区间数量和左右端点
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

/*
  解题思路: 区间合并,端点也算重叠,将有重叠的区间合并后输出
  1) 区间按左端点从小到大排序,有重叠则合并更新区间右端点
  2) range数组一个存储合并前的区间,一个存储合并后的区间,最后遍历输出即可
  
 */

const int N=1e5+5;

int n,a[N];

// range:原区间,ans:合并后区间
struct Range{
	int l;
	int r;
}range[N],ans[N];

// 可以直接return a.l<b.l ,如果右端点也从小到大排序则合并次数多了,常数反而大了
bool cmp(Range a,Range b) {
	if(a.l!=b.l) return a.l<b.l;
	return a.r<b.r;
}

int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		int l,r;
		cin>>l>>r;
		range[i]={l,r};
	}
	sort(range+1,range+1+n,cmp);
	// 枚举所有区间进行合并
	int cnt=0;
	ans[++cnt]=range[1]; // 结构体之间等价赋值

	for(int i=2;i<=n;i++) {
		// 可合并
		if(range[i].l<=ans[cnt].r) {
			ans[cnt].r=max(ans[cnt].r,range[i].r); // 更新右端点
		}
		// 不可合并,开新区间
		else {
			ans[++cnt]=range[i];
		}
	}
	cout<<cnt<<'\n'; // 区间个数
	// 输出合并后的区间
	for(int i=1;i<=cnt;i++) {
		cout<<ans[i].l<<' '<<ans[i].r<<'\n';
	}
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信