1. Problem Statement

You are given a list of non-overlapping intervals sorted by their start time. You are also given a new interval that needs to be inserted into the list. Insert the new interval such that the list remains sorted and non-overlapping. If necessary, merge overlapping intervals.

Constraints

The list is already sorted by interval start times.

Intervals are non-overlapping before insertion.

You need to maintain the sorted order and ensure no overlapping intervals in the result.

Example

Input:

Intervals = [[1, 3], [6, 9]]
New Interval = [2, 5]

Output:

[[1, 5], [6, 9]]

Explaination:

The new interval [2, 5] overlaps with [1, 3]. They merge into [1, 5].

2. Intuition and Approach

We handle the problem in three phases:

1. Add intervals that come before the new interval (no overlap).
2. Merge all intervals that overlap with the new interval.
3. Add intervals that come after the new interval (no overlap).

3. Step-by-Step Explanation

Let’s assume the input is a list of intervals intervals and a new interval newInterval.

Step 1: Initialize

• Create a result list result = [].
• Use an index i = 0 to iterate through the input list.

Step 2: Add All Intervals Before the New Interval

Add all intervals that end before the new interval starts. These can’t overlap.

while (i < intervals.length && intervals[i][1] < newInterval[0]) {
    result.add(intervals[i]);
    i++;
}

Step 3: Merge Overlapping Intervals

While there is overlap, keep merging:

• The condition for overlap is: interval[i][0] <= newInterval[1]
• Update the new interval to reflect the merged interval:
  • newInterval[0] = min(newInterval[0], intervals[i][0])
  • newInterval[1] = max(newInterval[1], intervals[i][1])

while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
    newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
    i++;
}
result.add(newInterval); // insert the merged interval

Step 4: Add Remaining Intervals

Add all the intervals after the merged interval.

while (i < intervals.length) {
    result.add(intervals[i]);
    i++;
}

4. Java Implementation

import java.util.*;

public class InsertInterval {
    public static int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        
        // Step 1: Add intervals before the new interval
        while (i < intervals.length && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        // Step 2: Merge overlapping intervals
        while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval);
        
        // Step 3: Add remaining intervals
        while (i < intervals.length) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {6, 9}};
        int[] newInterval = {2, 5};
        int[][] result = insert(intervals, newInterval);
        
        for (int[] interval : result) {
            System.out.print(Arrays.toString(interval) + " ");
        }
    }
}