Insert Interval

Given a sorted list of nonoverlapping intervals and a new interval, your task is to insert the new interval into the correct position while ensuring that the resulting list of intervals remains sorted and nonoverlapping. Each interval is a pair of nonnegative numbers, the first being the start time and the second being the end time of the interval.

Given a sorted list of nonoverlapping intervals and a new interval, your task is to insert the new interval into the correct position while ensuring that the resulting list of intervals remains sorted and nonoverlapping. Each interval is a pair of nonnegative numbers, the first being the start time and the second being the end time of the interval.

Constraints

• 0 ≤ existing_intervals.length ≤ 10⁴
• existing_intervals[i].length, new_interval.length == 2
• 0 ≤ start time < end time ≤ 10⁴
• The list of intervals is sorted in ascending order based on the start time.

Examples

Example 1

Input:

• Existing intervals: [1, 3], [5, 7], [8, 9], [10, 13]
• New interval: [2, 6]

Explanation: We will merge [2, 6] with the first interval, [1, 3], to create [1, 6], and then merge this interval with the next overlapping interval, [5, 7], to create [1, 7]. The intervals [8, 9] and [10, 13] don't overlap with any intervals, so they will exist independently.

Output: [1, 7], [8, 9], [10, 13]

Example 2

Input:

• Existing intervals: [1, 3], [6, 9]
• New interval: [2, 5]

Explanation: We will merge [2, 5] with the first interval, [1, 3], since they overlap, to create a new interval [1, 5]. The interval [6, 9] will exist independently, since it doesn't overlap with the other interval.

Output: [1, 5], [6, 9]

Insert Interval

Note: Only the solution and code were shared for this problem. The problem statement, constraints, and examples are missing. Please share them so the full article can be completed.

Solution

The steps to solve this problem:

• First, we find the correct place to insert the new interval. We loop through the array and compare each interval's starting value with the new interval's starting value.
• Once we find the correct spot, we check if the new interval overlaps with the interval already added before it.
  • If it overlaps, we update the last entry in our result.
  • If it does not overlap, we just add the new interval as it is.
• After inserting the new value, we go through the rest of the array. For each remaining interval, we check if it overlaps with the last entry in our result, and merge them if needed.

Code

function insertInterval(existingIntervals, newInterval) {
  let newStart = newInterval[0],
      newEnd = newInterval[1];
  let i = 0,
      n = existingIntervals.length;
  let output = [];

  while (i < n && newStart > existingIntervals[i][0]) {
    output.push(existingIntervals[i]);
    i = i + 1;
  }

  if (!output.length || output[output.length - 1][1] < newStart) {
    output.push(newInterval);
  } else {
    output[output.length - 1][1] = Math.max(output[output.length - 1][1], newEnd);
  }

  while (i < n) {
    let ei = existingIntervals[i];
    let start = ei[0],
        end = ei[1];
    if (output[output.length - 1][1] < start) output.push(ei);
    else output[output.length - 1][1] = Math.max(output[output.length - 1][1], end);
    i++;
  }

  return output;
}