LeetCode 57. Insert Interval
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:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
解析：
该题目是给定一组已经排序的区间列表，区间之间没有重合，插入一个新的区间并合并。题目类似于LeetCode56，只不过前一个是直接给定了列表区间，对列表区间进行合并。
解法1:
可以采用LeetCode 56的思路，先把插入的Interval追加到列表末尾，然后对整个列表按照start进行排序，然后合并重合的Interval，代码如下：
[cc lang=”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) {}
* };
*/
class Solution {
public:
static bool my_sort (Interval i,Interval j) { return (i.start
vector
if(intervals.empty())
{
result.push_back(newInterval);
return result;
}
intervals.push_back(newInterval);
sort(intervals.begin(), intervals.end(), my_sort);
Interval p = intervals[0];
for(int index =1; index < intervals.size(); index ++)
{
cout << "index:" << index << endl;
Interval cur = intervals[index];
if(cur.start <= p.end)
{
p.end = max(p.end, cur.end);
}else
{
result.push_back(p);
p = cur;
}
}
result.push_back(p);
return result;
}
};
[/cc]
运行结果如下：
可以看到花费的时间较长，主要原因在于初始列表已经排好序了，加入newInterval之后再次重新排序，消耗比较多的时间。
解法2:
列表中的每个元素与newInterval有3种情况，1:列表中的元素的end < newInterval.start，即列表中的元素在newInterval之前，这种情况下直接把元素插入到结果集中；2:列表中的元素与newInterval有重合，对元素进行合并，选择二者中最小的start作为新元素的start，选择二者中最大的end作为新元素的end，并把新元素赋值给newInterval;3.剩余元素直接追加到列表末尾。
具体代码如下：
[cc lang="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) {}
* };
*/
class Solution {
public:
vector
vector
vector
for(;it!=intervals.end(); it++)
{
if((*it).end < newInterval.start)
result.push_back(*it);
else if((*it).start > newInterval.end)
break;
else
{
newInterval.start = min(newInterval.start, (*it).start);
newInterval.end = max(newInterval.end, (*it).end);
}
}
result.push_back(newInterval);
for(; it!=intervals.end(); it++)
{
result.push_back(*it);
}
return result;
}
};
[/cc]
运行结果：
参考：
https://leetcode.com/problems/insert-interval/discuss/21632/Very-short-and-easy-to-understand-C++-solution
About Author
