贪心算法区间问题——选择不想交区间

た入场券 2022-05-09 07:04 284阅读 0赞

## 选择不想交的区间。 ##

数轴上有n个区间（ai,bi）。选择尽可能多个区间，使得这些区间没有公共点。

### 分析： ###

首先明确一个问题：假设有两个区间x,y，区间x完全包含y。那么，选x是不划算的，因为x和y最多选一个，选x不如选y，这样区间数目不会减少，而且给其他区间留下更多的位置。接下来，按照bi从小大大的顺序给区间排序。贪心算法策略是：**一定要选第一个区间**。为什么呢？

现在区间已经排序成b1<=b2<=......<=bn了，考虑a1和a2的大小关系。

情况一：a1>a2，如图a所示。包括之后所有被a1包含的区间都不选。

情况二：如图（b）所示，非完全相交。黑色部分木有什么影响，但灰色部分被下一个区间包含。由上面知，选第一个。

![70][]

题目：[https://blog.csdn.net/xia842655187/article/details/51944718][https_blog.csdn.net_xia842655187_article_details_51944718]

> 描述   
> 学校的小礼堂每天都会有许多活动，有时间这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校小礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能的安排更多的活动，请问他该如何安排。
> 
> 输入   
> 第一行是一个整型数m(m<100)表示共有m组测试数据。   
> 每组测试数据的第一行是一个整数n(n<1000)表示该测试数据共有n个活动。   
> 随后的n行，每行有两个正整数Bi,Ei(0<=Bi,Ei<10000),分别表示第i个活动的起始与结束时间（Bi<=Ei)
> 
> 输出   
> 对于每一组输入，输出最多能够安排的活动数量。   
> 每组的输出占一行   
> 样例输入   
> 2   
> 2   
> 1 10   
> 10 11   
> 3   
> 1 10   
> 10 11   
> 11 20   
> 样例输出   
> 1   
> 2
> 
> 提示   
> 注意：如果上一个活动在t时间结束，下一个活动最早应该在t+1时间开始
> 
> \--------------------- 本文来自 xia842655187 的CSDN 博客 ，全文地址请点击：https://blog.csdn.net/xia842655187/article/details/51944718?utm\_source=copy

代码：

#include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int maxn=20;
    
    struct timetable
    {
    	int a;
    	int b;
    }time[maxn];
    
    bool comp(timetable &x,timetable &y)//多看两遍 
    {
    	if(x.b!=y.b)
    		return (x.b<y.b);
    	if(x.a!=y.a) 
    		return (x.a<y.b);
    }
    
    
    int main()
    {
    	int i,n,count;
    	while(cin>>n)
    	{
    		count=1;
    		for(i=0;i<n;i++)//输入 
    		{
    			cin>>time[i].a;
    			cin>>time[i].b;
    		}
    		
    		sort(time,time+n,comp);//按b从小到大排序
    		
    		int newend=time[0].b;
    		cout<<"("<<time[0].a<<","<<time[0].b<<")"<<"  "; //第一个必然是 
    		for(i=1;i<n;i++)
    		{
    			if(newend<time[i].a)
    			{
    				count++;
    				newend=time[i].b;
    				cout<<"("<<time[i].a<<","<<time[i].b<<")"<<"  ";
    			}	
    		}
    		cout<<endl<<count<<endl; 	
    	}
    	return 0;
    }

参考文章：

[ACM知识点 之 贪心（2）选择不相交区间][https_blog.csdn.net_xia842655187_article_details_51944718]

[sort函数][sort]

[70]: /images/20220509/f410bbbac1824c95b3689a263f1009d6.png
[https_blog.csdn.net_xia842655187_article_details_51944718]: https://blog.csdn.net/xia842655187/article/details/51944718
[sort]: https://blog.csdn.net/sinat_38816924/article/details/82810769