首页 > 代码库 > 区间包括

区间包括

区间包括

个人信息:就读于燕大本科软件project专业 眼下大三;

本人博客:google搜索“cqs_2012”就可以;

个人爱好:酷爱数据结构和算法。希望将来从事算法工作为人民作出自己的贡献;

编程语言:C++ ;

编程坏境:Windows 7 专业版 x64;

编程工具:vs2008;

制图工具:office 2010 powerpoint;

硬件信息:7G-3 笔记本;


真言

夫妻没有隔夜仇。

题目

区间包括:给定一个源区间【x,y】和N个无序的目标区间【x1,y1】【x2,y2】【x3。y3】····【xn,yn】,推断源区间【x,y】是不是在目标区间内。

思路

先将源区间合并

第一步,源区间排序 O(n log n)

第二步。源区间相邻合并 O(n)

折半查找是否包括 O(log n)

算法

用c++代码设计例如以下

第一步:排序

//  区间按x轴排序
	void Qujian::Sort_Qujian_x(pair<int,int>* qujian,unsigned int length)
	{
	// 异常输入
		if(qujian == NULL || length == 0)
		{
			cout<<"异常输入"<<endl;
			return void(0);
		}

	// 正常输入
		else
		{
			qsort(qujian,length,sizeof(pair<int,int>),min_to_max_x);
			return void(0);
		}
	};
第二步:合并

// 区间集合压缩
	pair<pair<int,int>*,unsigned int> Qujian::Qujian_To_CutDown(pair<int,int> *qujian,unsigned int length)
	{
	// 异常输入
		if(qujian == NULL || length == 0)
		{
			cout<<"异常输入"<<endl;
			return make_pair((pair<int,int>*)0,0);
		}

	// 正常输入
		else{
		// 开辟最浪费的空间
			pair<int,int> * result = new pair<int,int>[length];
			Sort_Qujian_x(qujian,length);
			unsigned int i,j;

		// 核心算法
			// i 指向 result
			// j 指向 qujian
				i = 0;
				j = 0;
				result[i] = qujian[j];
				j++;
				while( j < length )
				{
				// 更新当前区间
					if( qujian[j].first <= result[i].second && qujian[j].second > result[i].second)
					{
						result[i].second = qujian[j].second;
						j++;
					}
				// 插入新区间
					else if( qujian[j].first > result[i].second )
					{
						i++;
						result[i] = qujian[j];
						j++;
					}
				}
				
			return make_pair(result,i+1);
		}
	};

第三步:折半查找是否包括

//  区间集合是否包括某一区间
	bool Qujian::Whether_including_Qujian(pair<int,int> * qujian,unsigned int length,pair<int,int> a)
	{
	// 对区间排序
		Sort_Qujian_x(qujian,length);

	// 合并区间
		pair<pair<int,int>*,unsigned int> newQujian = Qujian_To_CutDown(qujian,length);
		Show_Qujian(newQujian.first,newQujian.second);
	// 折半搜索区间
		unsigned int i = 0,j = newQujian.second - 1,center = (j-i)/2+i;
		while(i<j)
		{
			center=(j-i)/2+i;
			if( ((newQujian.first)[center]).first > a.first)
			{
				j = center - 1;
			}
			else 
			{
				i = center + 1;
			}
		}

	// 对折半结果进行处理
		if( i==j )
		{
		// 退到合适区间
			if( ((newQujian.first)[i]).first  > a.first )
			{
				if(i == 0)
					return false;
				else i--;
			}
		// 进行检查操作
			if(((newQujian.first)[i]).second  >= a.second )
				return true;
			else return false;
		}
		else
		{
			i = j;
		// 进行检查操作
			if(((newQujian.first)[i]).second  >= a.second )
				return true;
			else return false;
		}	
	};



区间包括