Insert Interval: Merging Intervals in Arrays

The "Insert Interval" problem is a common algorithmic challenge, involving the insertion and merging of intervals in a sorted list.

Problem Statement

Given a list of non-overlapping intervals sorted by their start times, insert a new interval into the list so that the list remains sorted and any overlapping intervals are merged.

Example

• Input: Intervals [[1,3],[6,9]], New Interval [2,5] Output: [[1,5],[6,9]] Explanation: The new interval [2,5] overlaps with [1,3] and should be merged into [1,5].

Solution Approach

function insert(intervals, newInterval) {
  let result = [];
  let i = 0;

  // Add all intervals ending before newInterval starts
  while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.push(intervals[i]);
    i++;
  }

  // Merge all overlapping intervals to one considering newInterval
  while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval = [
      Math.min(newInterval[0], intervals[i][0]),
      Math.max(newInterval[1], intervals[i][1]),
    ];
    i++;
  }
  result.push(newInterval); // Add the merged interval

  // Add all the rest
  while (i < intervals.length) {
    result.push(intervals[i]);
    i++;
  }

  return result;
}

Breaking Down the Solution

• Initial Non-Overlapping Intervals: Add all intervals that end before the new interval starts to the result.
• Merging Overlapping Intervals: Iterate through all intervals that overlap with the new interval and merge them into a single interval.
• Add Remaining Intervals: Finally, add the remaining intervals that start after the new interval ends.

Conclusion

The Insert Interval problem is an excellent example of interval manipulation and requires a careful approach to handle overlapping and merging. It is a common scenario in calendar and scheduling applications, making it a practical problem in software development.

Binary Search Solution

function insert(intervals, newInterval) {
  let left = 0,
    right = intervals.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (intervals[mid][1] < newInterval[0]) {
      left = mid + 1;
    } else if (intervals[mid][0] > newInterval[1]) {
      right = mid - 1;
    } else {
      newInterval = [
        Math.min(newInterval[0], intervals[mid][0]),
        Math.max(newInterval[1], intervals[mid][1]),
      ];
      intervals.splice(mid, 1);
      left = mid; // Adjust left to recheck the same mid index
    }
  }

  intervals.splice(left, 0, newInterval); // Insert the new/merged interval

  // Merge overlapping intervals if necessary
  let i = left;
  while (i < intervals.length - 1) {
    if (intervals[i][1] >= intervals[i + 1][0]) {
      intervals[i] = [intervals[i][0], Math.max(intervals[i][1], intervals[i + 1][1])];
      intervals.splice(i + 1, 1);
    } else {
      i++;
    }
  }

  return intervals;
}

Breaking Down the Solution

• Binary Search for Insertion Point: Use binary search to find the correct position or overlapping interval for the new interval.
• Insert and Merge: Insert the new interval at the found position. Then, iterate through the list to merge any overlapping intervals resulting from the insertion.
• Optimized Overlapping Check: Post-insertion, check only nearby intervals for any potential overlap, reducing the number of comparisons.

Conclusion

Using binary search in the Insert Interval problem significantly enhances the efficiency of finding the correct position for insertion, especially in cases with a large number of intervals. This approach exemplifies the power of combining binary search with interval merging for optimized solutions in array manipulation tasks.

Divide and Conquer solution

export function insertIntervalDivideAndConquer(
  intervals: [number, number][],
  newInterval: [number, number]
): [number, number][] {
  // Base case: if the intervals list is empty
  if (intervals.length === 0) {
    return [newInterval];
  }

  // Base case: if the intervals list contains only one interval
  if (intervals.length === 1) {
    return mergeIntervals(intervals[0], newInterval);
  }

  // Divide the intervals list into two halves
  const mid = Math.floor(intervals.length / 2);
  const leftPart = insertIntervalDivideAndConquer(intervals.slice(0, mid), newInterval);
  const rightPart = insertIntervalDivideAndConquer(intervals.slice(mid), newInterval);

  // Conquer: merge the two halves back together
  return mergeSortedIntervals(leftPart, rightPart);
}

// Helper function to merge two intervals if they overlap
function mergeIntervals(
  interval1: [number, number],
  interval2: [number, number]
): [number, number][] {
  if (interval1[1] < interval2[0] || interval2[1] < interval1[0]) {
    return [interval1, interval2].sort((a, b) => a[0] - b[0]);
  } else {
    return [[Math.min(interval1[0], interval2[0]), Math.max(interval1[1], interval2[1])]];
  }
}

// Helper function to merge two sorted lists of intervals
function mergeSortedIntervals(
  part1: [number, number][],
  part2: [number, number][]
): [number, number][] {
  let result = [],
    i = 0,
    j = 0;

  while (i < part1.length && j < part2.length) {
    let interval1 = part1[i],
      interval2 = part2[j];
    if (interval1[1] < interval2[0]) {
      result.push(interval1);
      i++;
    } else if (interval2[1] < interval1[0]) {
      result.push(interval2);
      j++;
    } else {
      const merged = mergeIntervals(interval1, interval2);
      result.push(...merged);
      i++;
      j++;
    }
  }

  while (i < part1.length) result.push(part1[i++]);
  while (j < part2.length) result.push(part2[j++]);

  return result;
}

In this solution:

1. The list of intervals is recursively split into two halves.
2. The mergeIntervals helper function is used to merge intervals if they overlap.
3. The mergeSortedIntervals function merges the two halves back together, ensuring that the result remains sorted and that all intervals are properly merged.

This approach is more complex than iterative solutions but showcases an alternative way of thinking about the problem.