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

HT·生活

123

 
 
 

日志

 
 

ex57 Insert Interval  

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

  下载LOFTER 我的照片书  |

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

原本是ex56的升级版,完全可以套用ex56函数,先插入,然后排序,然后合并。不过这样算法的复杂度就比较高了,而且这么做也比较傻,所以重新写了一个。添加了一个head和一个tail防止越界的,最后返回的时候把那两个剔除就可以了。重点在于重叠区间的判定,关于这个我写了不少注释,见代码

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> insert(vector<Interval>& intervals, Interval newInterval) {
int len = intervals.size();
result.clear();
if (len <= 0)
{
result.push_back(newInterval);
return result;
}

sort(intervals.begin(), intervals.end(), cmp); //先快排序

traverse(intervals, newInterval);
return result;
}
void traverse(vector<Interval> intervals, Interval newInterval)
{
Interval head(INT_MIN, INT_MIN), tail(INT_MAX, INT_MAX);
//加一个头 和 一个尾巴 避免下面越界
intervals.insert(intervals.begin(), head);
intervals.insert(intervals.end(), tail);
int len = intervals.size();
int ps, pe;
ps = 0;
pe = 0;
Interval current;
//循环融合
int i, j;
for (i = 0; i<len; i++)
{
if (intervals[i].start < newInterval.start)
{
ps++;
}
if (intervals[i].end < newInterval.end)
{
pe++;
}
}
//先把他们该插入的位置查找出来 一个是ps还有一个是pe
for (i = 0; i< ps - 1; i++)
{
result.push_back(intervals[i]);
}

////中间交错的区间判定
//if (newInterval.start>intervals[ps-1].end)
//{
// result.push_back(intervals[ps-1]);
// //newInterval和ps-1下标区间没有交差
//
// //接着判定newInterval.end是否和后面的区间有交差
// current.start = newInterval.start;
// if (newInterval.end >= intervals[pe].start)
// {
// current.end = intervals[pe].end;
// result.push_back(current);
// //有交叉,三个融合成一个了
// }
// else
// {
// //没有交差,一个current,还有一个是下标为pe的interval
// current.end = newInterval.end;
// result.push_back(current);
// result.push_back(intervals[pe]);
// }

//}
//else
//{
// //和前面一个区间有交差
// current.start = intervals[ps-1].start;
// //判定和pe是否有交差
// if (newInterval.end >= intervals[pe].start)
// {
// current.end = intervals[pe].end;
// result.push_back(current);
// //有交叉,三个融合成一个了
// }
// else
// {
// //没有较差,一个current,还有一个是下标为pe的interval
// current.end = newInterval.end;
// result.push_back(current);
// result.push_back(intervals[pe]);
// }
//}


//判定ps-1下标区间是否交差
if (newInterval.start>intervals[ps-1].end)
{
//newInterval和ps-1下标区间没有交差
result.push_back(intervals[ps-1]);

current.start = newInterval.start;
//当前的起点试试newInterval的start
}
else
{
//和前面一个区间有交差
current.start = intervals[ps-1].start;
}

//判定和pe是否有交差
if (newInterval.end >= intervals[pe].start)
{
current.end = intervals[pe].end;
result.push_back(current);
//有交叉,三个融合成一个了
}
else
{
//没有交叉,一个current,还有一个是下标为pe的interval
current.end = newInterval.end;
result.push_back(current);
result.push_back(intervals[pe]);
}



//后面没有交错区间的处理
pe++;
while (pe<len)
{
result.push_back(intervals[pe]);
pe++;
}
//去掉第一个元素 和最后一个区间
result.erase(result.begin());
result.erase(result.end()-1);

}
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