源于生活的活动安排问题及对贪心算法使用和验证

源于生活的活动安排问题及对贪心算法使用及验证

【问题描述】
现有一个阶梯教室，有n个活动(A1、A2、A3、A4…An)需要申请这个教室，但是这个教室同一时间只能被一个活动使用。已知每个活动的起始时间begin和结束时间end。问怎样安排活动才能使尽可能多的活动使用到教室。编写求出最多可以举办的活动数。
【问题分析】

• 算法模型：本题即转化为区间问题，在n个区间内，选择尽量多的区间，使得这些区间两两不相交
• 解决方法：从贪心算法的角度思考：
  • (1)贪心算法是一种自顶向下的求解方法，每次进行一次所谓的贪心策略选择之后，下一次只面对一个子问题
  • （2）既然（1）中明确了我们只需要面对一个子问题，也就是算法的时间复杂度是theta(n)。但是回过头来考虑此问题是否可以转化成通过贪心算法来进行求解呢？所以我们需要做的工作就是论证问题是适用于贪心算法的
  • (3) 明确贪心问题的两个重要特性：
    • a.论证问题符合贪心选择性
    • b.其最优结构特性
• 【回到问题】
  为了使每一次选择后，面对唯一的一个子问题，那我们就需要将活动按照结束时间end来进行单调递增的排序。
  • 其正确性：由于结束时间的单调递增排序，即排序后为end1<=end2<=end3<=end4…<=endn.用贪心策略进行选取活动，第一次选择的是A1，如果能证明A1必属于某一个全局最优解(全局最优解可能存在多个)，就可以证明问题的贪心选择性，即可以使用贪心算法进行求解。如何证明？
  • 假设已有全局最优解Sk，其中的Aj就是Sk中结束时间最早的活动，若A1=Aj,则问题得证，若A1！=Aj，由题可知，A1.end<=Aj.end.那么即使我们将Aj替换成A1得到的新的Sk’也是和原先的Sk相容的。因为他们的活动数是相同的，所以Sk’也是全局最优解。即A1必属于某个全局最优解。进而推出所有的局部贪心选择属于全局最优解中的一个子问题。
  • **换个角度：**倘若我们不选end1，假设选的是endi，则如果endi和end1不交叉，那肯定是多选一个end1是更优的选择；如果交叉，那endi换成end1才不影响后面的选择。

  ---

  【题解代码】

#include <iostream>

using namespace std;

int n,beg[1005],en[1005];

void init(){
	cin >> n;
	for(int i = 1; i<=n; i++){
		cin >> beg[i] >> en[i];
	}
}

void qsort(int x,int y){//快速排序 --按照时间的升序快速排序 
	int i,j,mid,t;
	i = x;
	j=y;
	mid = en[(x+y)/2];
	while(i<=j){
		while(en[i]<mid) i++;
		while(en[j]>mid) j--;
		if(i<=j){
			swap(en[i],en[j]);
			swap(beg[i],beg[j]);
			i++,j--;
		}
	}	
	if(x<j) qsort(x,j);
	if(i<y) qsort(i,y);
}

void solve(){
	int ans = 0;
	for(int i = 1,t = -1;i<=n;i++){//t=-1是用于对第一个区间与其他区间的操作相同,否则需要单独处理第一个区间 
		if(beg[i]>=t){
			ans++;
			t = en[i];
		} 
	}
	cout << ans <<endl;	
}
 

int main(){
	freopen("huodong.txt","r",stdin); //输入重定向，输入数据将从in.txt文件中读取
    freopen("changshu.txt","w",stdout); //输出重定向，输出数据将保存在out.txt文件中
	init();
	qsort(1,n);//对n组数据进行排序
	solve();

	return 0;
}