注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex56 Merge Intervals  

2015-05-25 22:13:14|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

就是给了一堆区间,现在需要把多余的区间给去掉,普通的去重复元素的算法,最重要的一点就是一定要算好下标,否则就比较坑爹了,下一题是关于插入的,恶心死了。见c++代码

//Definition for an interval.
struct Interval {
int start;
int end;
Interval() : start(0), end(0) {}
Interval(int s, int e) : start(s), end(e) {}
};

bool cmp(Interval a, Interval b)
{
if (a.start == b.start)
{
return a.end > b.end;
}
else
{
return a.start < b.start;
}

}
class Solution {
public:
vector<Interval> result;
vector<Interval> merge(vector<Interval>& intervals) {
int len = intervals.size();
result.clear();
if (len <= 0)
return result;
sort(intervals.begin(), intervals.end(), cmp); //先快排序

traverse(intervals);
return result;
}
void traverse(vector<Interval> intervals)
{
int len = intervals.size();
int ps, pe;
ps = 0;
pe = 0;
Interval current,node;
//循环融合
while (ps<len)
{
current = intervals[ps];
//pointer = intervals[pe + 1];
while ((pe + 1)<len&&current.end >= intervals[pe + 1].start)
{
//如果当前的end和下一个start有重叠的话,就融合,因为我们已经排过序列了
//小的在前面
current.end = myMax(current.end, intervals[pe + 1].end);
pe++;
}
result.push_back(current);
pe++;
ps = pe;
}
}
int myMin(int a,int b)
{
return a>b ? b : a;
}
int myMax(int a, int b)
{
return a > b ? a : b;
}
};


  评论这张
 
阅读(8)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017