57. Insert Interval

Problem

https://leetcode.com/problems/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].

Solution

• use Array.prototype.splice()
  like this intervals.splice(startIndex, deleteCount, insertedInteval)
• two edge cases
  • newInterval.start needs to extend.
    for example: [[1,5]] and [3,4]
  • newInterval.end needs to extend.
    for example: [[1,5]] and [0,3]

/**
 * 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) {
    if (intervals.length <= 0) {
        return [newInterval]
    }

    // if (newInterval.end < intervals[0].start) {
    //     intervals.unshift(newInterval)
    //     return intervals
    // }

    // if (newInterval.start > intervals[intervals.length-1].end) {
    //     intervals.push(newInterval)
    //     return intervals
    // }
    let insertedInterval = new Interval(newInterval.start, newInterval.end)

    let startIndex
    for (startIndex = 0; startIndex < intervals.length; startIndex += 1) {
        if (newInterval.start < intervals[startIndex].start) {
            break
        }
    }

    if (startIndex > 0 && newInterval.start <= intervals[startIndex-1].end) {
        if (newInterval.end <= intervals[startIndex-1].end) {
            // [intervals[startIndex-1]]
            //      [newInterval]
            return intervals
        }
        // [intervals[startIndex-1]]
        //                 [newInterval]
        startIndex -= 1
        insertedInterval.start = intervals[startIndex].start
    }

    let endIndex
    for (endIndex = startIndex; endIndex < intervals.length; endIndex += 1) {
        if (newInterval.end < intervals[endIndex].end) {
            break
        }
    }

    let deleteCount = endIndex - startIndex

    if (endIndex < intervals.length && newInterval.end >= intervals[endIndex].start) {
        //      [intervals[endIndex]]
        // [newInterval]
        deleteCount += 1
        insertedInterval.end = intervals[endIndex].end
    }

    intervals.splice(startIndex, deleteCount, insertedInterval)

    return intervals
};