LeetCode 057 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:
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].
题目大意：
对于给出的互不重叠且按照左端点排序的区间序列，将一个新的区间插入到这个序列当中（合并重叠的区间），使其仍然保持原本的性质。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
intervals.append(newInterval)
intervals.sort(key=lambda x: x[0])
new_interval = [intervals[0][0], intervals[0][0]]
res = []
for interval in intervals:
if self.can_merge(new_interval, interval):
new_interval = self.merge_two_intervals(new_interval, interval)
else:
res.append(new_interval)
new_interval = interval
res.append(new_interval)
return res
def can_merge(self, interval, interval2):
return interval[1] >= interval2[0]
def merge_two_intervals(self, interval, interval2):
return [interval[0], max(interval[1], interval2[1])]
|
解题思路：
与L56题基本一致，但单元测试更加严格，加入含最大整数值的区间。
- 先找到start大于等于待插入区间的区间，然后待插入区间插入其前。
- 归结成L56题
注意事项：
- 先找到start大于等于待插入区间的区间，然后待插入区间插入其前。
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
j = 0
while j < len(intervals):
if intervals[j][0] >= newInterval[0]:
break
j += 1
intervals.insert(j, newInterval)
new_interval = [intervals[0][0], intervals[0][0]]
res = []
for interval in intervals:
if self.can_merge(new_interval, interval):
new_interval = self.merge_two_intervals(new_interval, interval)
else:
res.append(new_interval)
new_interval = interval
res.append(new_interval)
return res
def can_merge(self, interval, interval2):
return interval[1] >= interval2[0]
def merge_two_intervals(self, interval, interval2):
return [interval[0], max(interval[1], interval2[1])]
|
注意事项：
判断是否合并的API中，加入in2.start == Integer.MAX_VALUE返回false。
Java代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
int st = 0;
for(;st<intervals.size();st++){
if(intervals.get(st).start>=newInterval.start){
break;
}
}
intervals.add(st, newInterval);
intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE));
List<Interval> re = new ArrayList<Interval>();
Interval newInterval2 = null;
for(int i=1;i<intervals.size();i++){
if(newInterval2==null)
newInterval2 = intervals.get(i-1);
if(canMerge(newInterval2,intervals.get(i))){
newInterval2 = mergeIntervals(newInterval2,intervals.get(i));
}
else{
re.add(newInterval2);
newInterval2 = null;
}
}
return re;
}
|
算法分析：
时间复杂度为O(n)，空间复杂度O(1)，因为不用排序。
Follow-up:
- 先解出L56
- 再解此题
