【Insert Interval】cpp
题目：
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].
代码：
/**
* 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> ret;
int i = ;
// search for start insert position
for ( ; i<intervals.size(); ++i )
{
if ( newInterval.start > intervals[i].end )
{
ret.push_back(intervals[i]);
}
else
{
break;
}
}
// newInterval larger than all the existed intervals
if ( i==intervals.size() )
{
ret.push_back(newInterval);
return ret;
}
int start = std::min( intervals[i].start, newInterval.start );
// search for the end insert position
for ( ;i<intervals.size();++i )
{
if ( newInterval.end <= intervals[i].end ) break;
}
// newInterval end is larger than all the range
if ( i==intervals.size() )
{
ret.push_back(Interval(start, newInterval.end));
return ret;
}
if ( newInterval.end<intervals[i].start )
{
ret.push_back(Interval(start,newInterval.end));
ret.insert(ret.end(), intervals.begin()+i, intervals.end());
return ret;
}
if ( newInterval.end==intervals[i].start )
{
ret.push_back(Interval(start,intervals[i].end));
if ( i<intervals.size()- )
{
ret.insert(ret.end(), intervals.begin()+i+, intervals.end());
}
return ret;
}
if ( newInterval.end > intervals[i].start )
{
ret.push_back(Interval(start,intervals[i].end));
if ( i<intervals.size()- )
{
ret.insert(ret.end(), intervals.begin()+i+,intervals.end());
}
return ret;
}
}
};
tips：
这道题的总体感觉就是很繁琐，因为要考虑各种边界情况，等或者不等；虽然能AC但是这一版代码比较丑陋。
看能不能改一版漂亮一些的。
===================================
学习了一个迭代版的，代码很漂亮，但是会超时。
/**
* 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>::iterator it = intervals.begin();
while ( it!=intervals.end() )
{
if ( newInterval.end < it->start )
{
intervals.insert(it, newInterval);
return intervals;
}
else if ( it->end < newInterval.start )
{
it++;
}
else
{
newInterval.start = std::min(newInterval.start, it->start);
newInterval.end = std::max(newInterval.end, it->end);
intervals.erase(it);
}
}
intervals.insert(intervals.end(), newInterval);
return intervals;
}
};
=======================================
还是觉得自己的第一次AC的代码太乱，网上搜了一下，模仿大神（http://yucoding.blogspot.sg/2013/01/leetcode-question-35-insert-interval.html）重新写了一版AC的代码。
/**
* 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> ret;
// insert the new Interval
vector<Interval>::iterator it = intervals.begin();
for( ; it!=intervals.end(); ++it )
{
if ( newInterval.start < it->start )
{
intervals.insert(it, newInterval);
break;
}
}
if ( it==intervals.end() )
{
intervals.insert(it, newInterval);
}
// merge the intervals
ret.push_back(*intervals.begin());
for ( it=intervals.begin()+; it!=intervals.end(); ++it )
{
if ( it->start > ret.back().end )
{
ret.push_back(*it);
}
else
{
ret.back().start = std::min(ret.back().start, it->start);
ret.back().end = std::max(ret.back().end, it->end);
}
}
return ret;
}
};
tips:
这一版的代码采用了新的思路。
1. 题中给定了原有的interval集合是按照start排好序的；因此，首先要找到合适的位置，将newInterval插进去。
2. 插进去之后，就有可能存在intervals之间存在overlap的情况，因此再merge（http://www.cnblogs.com/xbf9xbf/p/4557153.html）一遍就OK。
在merge的过程中有个细节：不用维护start和end，ret.back().start和ret.back().end就可以。这个比自己原来写的merge intervals要好，学习了这个细节。
=============================================
第二次过这道题，直接参照的最简洁的思路：
（1）先insert：条件是i->end > newInterval.start（即肯定有重叠） 根据newInterval.start的大小先插进去
（2）再merge：修改ret.back().start和ret.back().end的值
/**
* 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> ret;
vector<Interval>::iterator i=intervals.begin();
for ( ; i!=intervals.end(); ++i )
{
if ( i->end > newInterval.start ){
intervals.insert(i, newInterval);
break;
}
}
if ( i==intervals.end() ) intervals.insert(i, newInterval);
ret.push_back(*intervals.begin());
for ( i=intervals.begin()+; i!=intervals.end(); ++i )
{
if ( i->start > ret.back().end )
{
ret.push_back(*i);
}
else
{
ret.back().start = min(ret.back().start, i->start);
ret.back().end = max(ret.back().end, i->end);
}
}
return ret;
}
};
=========================================
第三次过这道题，终于理清楚了。
类似这样的图形去理解interval insert 和 merge
1
11
111
111
11
1
最新文章
- php下载远程文件方法~
- typeof知多少
- Coax Transformers[转载]
- SQL Server的三种物理连接之Hash Join（三）
- [zz]安装PostgreSQL数据库(Linux篇)
- 关于WPF中承载 ArcGIS控件。
- SPARK 学习笔记一
- Python3中性能测试工具Locust安装使用
- [转帖]Oracle 补丁体系(PSR/PSU/CPU) 及 opatch 工具 介绍
- 关于MySQL常用的查询语句
- Django手册
- gulp报错task function must be specified
- 彻底弄懂css中单位px和em，rem的区别
- SQL 查询结果加序列号
- hiredis安装及测试
- 【python】格式化字符
- js模态窗口返回值(table)
- ASP.Net Core 2.2 MVC入门到基本使用系列 (一)
- servlet实现文件上传，预览，下载和删除
- javaWeb中的文件上传下载