Problem
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 (Java)
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
int n = intervals.length;
int l = 0;
int r = n - 1;
while (l < n && newInterval[0] > intervals[l][1]) {
l++;
}
while (r >= 0 && newInterval[1] < intervals[r][0]) {
r--;
}
int[][] res = new int[l + n - r][2];
for (int i = 0; i < l; i++) {
res[i] = Arrays.copyOf(intervals[i], intervals[i].length);
}
res[l][0] = Math.min(newInterval[0], l == n ? newInterval[0] : intervals[l][0]);
res[l][1] = Math.max(newInterval[1], r == -1 ? newInterval[1] : intervals[r][1]);
for (int i = l + 1, j = r + 1; j < n; i++, j++) {
res[i] = intervals[j];
}
return res;
}
}
Solution (Javascript)
/**
* Definition for an interval.
* function Interval(start, end) {
* this.start = start;
* this.end = end;
* }
*/
/**
* @param {Interval[]} intervals
* @param {Interval} newInterval
* @return {Interval[]}
*/
var insert = function(intervals, newInterval) {
var len = intervals.length;
var i = 0;
var res = [];
while (i < len && intervals[i].end < newInterval.start) {
res.push(intervals[i]);
i++;
}
while (i < len && intervals[i].start <= newInterval.end) {
newInterval.start = Math.min(newInterval.start, intervals[i].start);
newInterval.end = Math.max(newInterval.end, intervals[i].end);
i++;
}
res.push(newInterval);
while (i < len) {
res.push(intervals[i]);
i++;
}
return res;
};
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).