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]
.
Solution
(1) Java
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> rst = new ArrayList<>();
for (Interval it : intervals) {
if (newInterval.end < it.start) {
rst.add(newInterval);
newInterval = it;
} else if (newInterval.start > it.end) {
rst.add(it);
} else {
newInterval.start = Math.min(newInterval.start, it.start);
newInterval.end = Math.max(newInterval.end, it.end);
}
}
rst.add(newInterval);
return rst;
}
}
(2) Python
(3) Scala