題目鏈接
tag:
- Hard忿磅；
question：
??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].
思路：
??本題讓在一系列非重疊的區(qū)間中插入一個(gè)新的區(qū)間柴信，可能還需要和原有的區(qū)間合并，那需要對(duì)給區(qū)間集一個(gè)一個(gè)的遍歷比較泌神，那么會(huì)有兩種情況飞几，重疊或是不重疊血崭，不重疊的情況好辦擅羞，直接將新區(qū)間插入到對(duì)應(yīng)的位置即可，重疊的情況比較復(fù)雜蝗罗，有時(shí)候會(huì)有多個(gè)重疊艇棕，需要更新新區(qū)間的范圍以便包含所有重疊蝌戒，之后將新區(qū)間加入結(jié)果res，最后將后面的區(qū)間再加入結(jié)果即可沼琉。
??具體思路是北苟，我們用一個(gè)變量cur來遍歷區(qū)間，如果當(dāng)前cur區(qū)間的結(jié)束位置小于要插入的區(qū)間的起始位置的話打瘪，說明沒有重疊友鼻，則將cur區(qū)間加入結(jié)果res中，然后cur自增1闺骚。直到有cur越界或有重疊while循環(huán)退出彩扔，然后再用一個(gè)while循環(huán)處理所有重疊的區(qū)間，每次用取兩個(gè)區(qū)間起始位置的較小值僻爽，和結(jié)束位置的較大值來更新要插入的區(qū)間虫碉，然后cur自增1。直到cur越界或者沒有重疊時(shí)while循環(huán)退出胸梆。之后將更新好的新區(qū)間加入結(jié)果res敦捧，然后將cur之后的區(qū)間再加入結(jié)果res中即可，代碼如下：
/**
* 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;
int n = intervals.size(), cur = 0;
while (cur < n && intervals[cur].end < newInterval.start) {
res.push_back(intervals[cur++]);
}
while (cur < n && intervals[cur].start <= newInterval.end) {
newInterval.start = min(newInterval.start, intervals[cur].start);
newInterval.end = max(newInterval.end, intervals[cur].end);
++cur;
}
res.push_back(newInterval);
while (cur < n) {
res.push_back(intervals[cur++]);
}
return res;
}
};
