首页 > 代码库 > 【数学】【排序】用最少的点,访问数组中的所有区间
【数学】【排序】用最少的点,访问数组中的所有区间
题目: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; }
【数学】【排序】用最少的点,访问数组中的所有区间
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。