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] .
Given intervals
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] .
Given
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10] .
<Solution>這題和 merge intervals 算是姊妹題
不同的地方是,這題是要 insert 一個 newInterval 進來
並且把 overlap 的 interval 都拿掉,用最大的 interval 取代
解題想法如下(參考資料)
- 直接對原 vector 做操作,所以使用 iterator
- 當 newInterval.end 小於當前 interval.start,代表找到插入點了,離開迴圈
- 當 newInterval.start 大於當前 interval.end,沒有 overlap,什麼都不做
- 當不符合上述兩種情況,代表和當前 interval 有 overlap,這時候把 overlap 區間的最小值給 newInterval.start,最大值給 newInterval.end,overlap 的 counter 加1
- 從迴圈離開後,看看是否有 overlap,有的話就全部刪除
- 插入 newInterval
c++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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) { | |
auto it = intervals.begin(); | |
int overlap = 0; | |
while(it != intervals.end()) { | |
if(newInterval.end < it->start) { | |
//> newInterval must one before current it | |
break; | |
} | |
else if(it->end < newInterval.start) { | |
//> do nothing | |
} | |
else { | |
//> overlapping | |
newInterval.start = min(newInterval.start, it->start); | |
newInterval.end = max(newInterval.end, it->end); | |
++overlap; | |
} | |
++it; | |
} | |
if(overlap != 0) { | |
//> remove overlaps | |
it = intervals.erase(it - overlap, it); | |
} | |
intervals.insert(it, newInterval); | |
return intervals; | |
} | |
}; |
Kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> { | |
var overlapCount = 0 | |
var index = 0 | |
loop@ while(index < intervals.size) { | |
when { | |
intervals[index][1] < newInterval[0] -> {} | |
intervals[index][0] > newInterval[1] -> break@loop | |
else -> { | |
newInterval[0] = Math.min(newInterval[0], intervals[index][0]) | |
newInterval[1] = Math.max(newInterval[1], intervals[index][1]) | |
++overlapCount | |
} | |
} | |
++index | |
} | |
val tmpIntervals = intervals.toMutableList() | |
val insertIndex = index - overlapCount | |
while(overlapCount > 0) { | |
tmpIntervals.removeAt(insertIndex) | |
--overlapCount | |
} | |
tmpIntervals.add(insertIndex, newInterval) | |
return tmpIntervals.toTypedArray() | |
} | |
} |
沒有留言:
張貼留言