2016年12月12日 星期一

[LeetCode] 57. Insert Interval

轉自LeetCode

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].
<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
code如下

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<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
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()
}
}

沒有留言:

張貼留言