leetcode Insert Interval 区间插入

作者:jostree  转载请注明出处 http://www.cnblogs.com/jostree/p/4051169.html

题目链接:leetcode Insert Interval

使用模拟的方法,把需要插入的区间和每一个给定的区间进行比较,有三种情况:

1.给定区间的起点小于要插入区间的终点,并且区间还未被查入过,那么插入区间。

2.给定区间的终点大于要插入区间的起点,或者插入区间已经被插入过了,那么插入给定区间。

3.不满足以上两种情况,说明给定区间与插入区间有交集,那么把需要插入的区间修改为其并集。

代码中的标记位inserted,标记需要插入的区间是否被插入到了结果中。

代码如下:

 /**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class Solution {
public:
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval)
{
vector<Interval> res;
bool inserted = ;
for( int i = ; i < intervals.size() ; i++ )
{
if( intervals[i].start > newInterval.end && inserted == )
{
res.push_back(newInterval);
res.push_back(intervals[i]);
inserted = ;
}
else if( intervals[i].end < newInterval.start || inserted== )
{
res.push_back(intervals[i]);
}
else
{
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
}
}
if( inserted == )
{
res.push_back(newInterval);
}
return res;
} };
上一篇:PHP中调用外部命令的方法


下一篇:codeforces 578b//"Or" Game// Codeforces Round #320 (Div. 1)