#311 Insert New Interval

Given:

• Array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i]
• A new interval newInterval = [start, end]
• intervals is sorted by start time

Insert newInterval into intervals such that:

• Result remains sorted by start time
• No overlapping intervals (merge if needed)
• Return the resulting intervals array

Constraints:

• 0 ≤ intervals.length ≤ 1000
• newInterval.length == intervals[i].length == 2
• 0 ≤ start ≤ end ≤ 1000

Examples:

// Example 1:

console.log(insert([[1,3],[4,6]], [2,5]));
// Output: [[1,6]]

// Explanation: [2,5] overlaps with both intervals


// Example 2:

console.log(insert([[1,2],[3,5],[9,10]], [6,7]));
// Output: [[1,2],[3,5],[6,7],[9,10]]

// Explanation: [6,7] fits between existing intervals