Insert Interval

You are given an array of non-overlapping intervals intervals,

where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.

You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

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

Insert Interval Java Solution With Linear Search Approach

we will need to insert the newInterval into the original list keeping the start value of intervals in ascending order.

So, the new problem is given N intervals in ascending order of the start and another interval, newInterval, insert the newInterval in the list in the order of its start value.

This can be done using linear search, we can iterate over the intervals in the list, and the newInterval should be inserted just before the interval having a greater start value.

This way, we can produce the list of intervals in ascending order of their start value and solve it using the algorithm

Insert Interval and Merge Overlapping Intervals

    
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        intervals = insertIntervalFun(intervals, newInterval);
        
        List answer = new ArrayList<>();
        for(int i = 0; i < intervals.length; i++){
            int[] currentInterval = {intervals[i][0], intervals[i][1]};
            
            //merge 
            //no overlapping found
            while(i < intervals.length && isOverlap(currentInterval, intervals[i])){
                currentInterval = mergeIntervals(currentInterval, intervals[i]);
                i++;
            }
            i--;
            answer.add(currentInterval);
        }
        
        return answer.toArray(new int[answer.size()][2]); 
    }
    
    int[] mergeIntervals(int x[], int[] y){
        int[] interval_new = {Math.min(x[0], y[0]),  Math.max(x[1], y[1])}; 
        return interval_new;
    }
    
    boolean isOverlap(int[] x, int[] y){
        return Math.min(x[1], y[1]) - Math.max(x[0], y[0]) >= 0;
    }
    
    int[][] insertIntervalFun(int[][] intervals, int[] newInterval){
        boolean isInsertedNewInterval = false;        
        List list = new ArrayList<>(Arrays.asList(intervals));
        
        for(int i = 0; i < intervals.length; i++){
            if(newInterval[0] < intervals[i][0]){
                //we have found our position to insert this new interval
                list.add(i, newInterval);
                isInsertedNewInterval = true;
                break;
            }   
        }
        
        if(!isInsertedNewInterval){
            list.add(newInterval);
        }
        
        return list.toArray(new int[list.size()][2]);
    }
}        
    

Explanation

This code inserts a new interval into a list of intervals and merges any overlapping intervals.

Key Methods

• insert: The main function that handles the interval insertion and merging.
• mergeIntervals: Merges two overlapping intervals into one.
• isOverlap: Checks whether two intervals overlap.
• insertIntervalFun: Finds the correct position to insert the new interval and returns the updated list of intervals.

Algorithm

1. Call the helper function insertIntervalFun to insert the new interval into its correct position in the list of intervals.

2. Iterate through the intervals and merge any overlapping intervals:

   • For each interval, initialize it as the currentInterval.

   • If the next interval overlaps with the currentInterval, merge them into one interval using mergeIntervals.

   • Continue merging overlapping intervals until no more overlaps are found.

   • Add the merged interval to the result list.

3. Convert the result list into a 2D array and return it.

Complexity Analysis

• Time Complexity: O(n)

  • The insertion operation in insertIntervalFun runs in O(n) as it iterates through the intervals to find the correct position for the new interval.

  • The merging operation iterates through all intervals once, also taking O(n).

• Space Complexity: O(n)

  • Additional space is used for the result list and the auxiliary data structures during merging.

Approach 2: Binary Search

The only difference with this approach would be that instead of using linear search to find the suitable position of newInterval,

we can use binary search as the list of intervals is sorted in order of their start time.

We need to find the first interval in the list intervals having a start value greater than the start value of newInterval.

Apart from this change, the logic remains the same for this approach;

we insert the interval at its place using binary search and then merge the overlapping intervals using the same algorithm we used previously.

    
class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        intervals  = insertIntervalfun(intervals, newInterval);
        
        List answer_interval_list = new ArrayList<>();
        for(int i = 0; i < intervals.length; i++){
            int[] currentInterval = {intervals[i][0], intervals[i][1]};
            
            //continue merge
            //no overlappinng
            while(i < intervals.length && isOverlappingInterval(currentInterval, intervals[i])){
                currentInterval = mergeIntervals(currentInterval, intervals[i]);
                i++;
            }
            i--;
            answer_interval_list.add(currentInterval);
        }
        
        return answer_interval_list.toArray(new int[answer_interval_list.size()][2]);
    }
    
    int[] mergeIntervals(int[] x, int[] y){
        int[] newInterval = {Math.min(x[0], y[0]), Math.max(x[1],y[1])};
        return newInterval;
    }
    
    boolean isOverlappingInterval(int[] x, int[] y){
        return Math.min(x[1], y[1]) - Math.max(x[0], y[0]) >= 0;
    }
    
    int[][] insertIntervalfun(int[][] intervals, int[] newInterval){
        List list = new ArrayList<>(Arrays.asList(intervals));
        int index = UpperBoundFun(intervals, newInterval);
        
        if(index != intervals.length){
            list.add(index, newInterval);
        }else{
            list.add(newInterval);
        }
        
        return list.toArray(new int[list.size()][2]);
    }
    
    int UpperBoundFun(int[][] intervals, int[] newInterval){
        if(intervals.length == 0){
            return 0; //if interval is empty then add on 0 index
        }
        
        int start = 0;
        int end = intervals.length - 1;
        int answer = intervals.length;
        
        while(start <= end){
            int mid = (start + end)/2;
            if(intervals[mid][0] > newInterval[0]){
                answer = mid;
                end = mid - 1;
            }
            else{
                start = mid + 1;
            }
        }
        return answer;
    }
}        
    

Explanation

This code inserts a new interval into a list of intervals, maintaining order, and merges any overlapping intervals.

Key Methods

• insert: The main method that handles insertion and merging of intervals.
• mergeIntervals: Merges two overlapping intervals into a single interval.
• isOverlappingInterval: Checks if two intervals overlap.
• insertIntervalfun: Inserts the new interval into the correct position in the list.
• UpperBoundFun: Finds the appropriate index for the new interval using binary search.

Algorithm

1. Call insertIntervalfun to insert the new interval into its correct position using binary search for efficiency.

2. Iterate through the updated intervals:

   • Initialize currentInterval as the current interval.

   • Merge overlapping intervals using mergeIntervals.

   • Continue merging until no overlaps are found, then add the merged interval to the result list.

3. Convert the result list to a 2D array and return it.

Complexity Analysis

• Time Complexity: O(n log n)

  • Binary search in UpperBoundFun runs in O(log n).

  • The merging operation iterates through all intervals in O(n).

• Space Complexity: O(n)

  • Additional space is used for the result list and auxiliary data structures.