Here is my solution. It's break a loop into three sections:
1. Find the new begin number to construct new interval.
2. Find the new end number to construct new interval.
3. Append the remaining items into new interval.
Hope this make sense.
Also, hope those if/else conditions can be more straight forward.
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
let begin = newInterval[0];
let end = newInterval[1];
let result = [];
let tmpInterval = [];
let len = intervals.length;
let i = 0;
if (len == 0) {
return [newInterval]
}
// 1. insert begin position
for (i = 0; i < len; i++) {
let interval = intervals[i];
if (begin <= interval[0]) {
tmpInterval[0] = begin;
break;
} if (begin > interval[0] && begin <= interval[1]) {
tmpInterval[0] = interval[0];
break;
} else if (begin > interval[1]) {
result.push(interval);
if (i===len-1){
result.push(newInterval);
}
}
}
// 2. insert end position
for (; i < len; i++) {
let interval = intervals[i];
if (end < interval[0]) {
tmpInterval[1] = end;
result.push(tmpInterval);
break;
} else if (end <= interval[1]) {
tmpInterval[1] = interval[1];
result.push(tmpInterval);
i++;
break;
} else if (end > interval[1]) {
if (i===len-1) {
tmpInterval[1] = Math.max(interval[1], end);
result.push(tmpInterval);
}
continue;
}
}
// 3. remaining interval
for (; i < len; i++) {
let interval = intervals[i];
result.push(interval);
}
return result;
};
Try to get one step further. Now, just put newInterval into array in order.
Then swap the end number.
The logic in here is getting more straight forward.
/**
* @param {number[][]} intervals
* @param {number[]} newInterval
* @return {number[][]}
*/
var insert = function(intervals, newInterval) {
let len = intervals.length;
// base cases
if (len == 0) {
return [newInterval]
}
if (newInterval[1] < intervals[0][0]) {
return [newInterval, ...intervals];
}
if (newInterval[0] > intervals[len-1][1]) {
return [...intervals, newInterval];
}
// merge newInterval into interval in order,
// but the end number
let found = false;
let tmpIntervals=[]
for (let i=0; i<len; i++) {
let interval = intervals[i];
if (!found && newInterval[0] <= interval[0]) {
tmpIntervals.push([...newInterval]);
found = true;
}
tmpIntervals.push([...interval]);
}
if (!found) {
tmpIntervals.push([...newInterval]);
}
// fix the end number by swapping
let last = tmpIntervals[0];
let result = [last];
for (let i=1; i<tmpIntervals.length; i++) {
let interval = tmpIntervals[i];
if (interval[0]<=last[1]) {
last[1] = Math.max(last[1], interval[1]);
} else {
last = interval
result.push(last);
}
}
return result;
};
No comments:
Post a Comment