首页 > 代码库 > 【数学】【排序】用最少的点,访问数组中的所有区间

【数学】【排序】用最少的点,访问数组中的所有区间

题目:EPI  13.12

技术分享

我的代码与书上的代码略有不同,是从题目13.11中得到的启发。方法是先把数组A排序,然后用一个变量cur记录当前已经遍历的区间的交集,cur初始化为A[0],从A[1]开始遍历数组,若当前遍历到的元素A[i] 与 cur有交集,则更新cur;若没有交集,则从cur中选一个点填入返回值res,然后cur=A[i]。

typedef int TimeType;

class Interval
{
public:
	TimeType left,right;
	Interval(const TimeType &a,const TimeType &b):left(a),right(b){}
	const bool operator<(const Interval &a)const
	{
		if(left!=a.left)
			return left<a.left;
		else 
			return right<a.right;
	}
};

vector<TimeType> covering(vector<Interval>  A)
{
	vector<TimeType> res;
	if(A.empty())
		return res;
	sort(A.begin(),A.end());
	Interval cur=A[0];//记录当前区间的交集
	for(int i=1;i<A.size();i++)
	{
		//肯定有cur<=A[i]
		if(A[i].left<=cur.right)//有交集
		{
			//缩小cur范围
			int r=min(cur.right,A[i].right);
			cur.left=A[i].left;
			cur.right=r;
		}
		else
		{
			res.push_back(cur.right);
			cur=A[i];
		}
	}
	res.push_back(cur.right);
	return res;
}


【数学】【排序】用最少的点,访问数组中的所有区间