Solution For Insert Interval

Problem Statement:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

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

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Approach:

The given problem can be efficiently solved using two pointers. First, we will iterate over the intervals, and we will stop as soon we find the last interval that starts before our new interval. Using another pointer, we will go over the remaining intervals. In each iteration, we will check whether the current interval ends before the start of our new interval or whether our new interval ends before the start of the current interval. In these two cases, we do not need to merge intervals. Otherwise, there is an overlap between the current interval and our new interval. We will create a new interval that represents the merged intervals, add it to our output, and continue iterating over the remaining intervals.

Algorithm:

1. Initialize index variable to point at 0-th position of the interval list
2. Iterate over the interval list as long as we do not reach the end of the list or the start of a new interval.
3. If the end of the current interval is less than the start of the new interval, increase the index variable to move to the next interval.
4. If the start of the current interval is greater than the end of the new interval, insert the new interval starting from the current index.
5. If there is an overlap between the current interval and the new interval, create a new merged interval.
6. Add remaining intervals to the merged interval as long as there is an overlap.
7. If there is no overlap with remaining intervals return the result.

Time Complexity:

The time complexity of the given algorithm is O(N), where N is the number of intervals in the input.

Space Complexity:

The space complexity of the given algorithm is O(N), where N is the number of intervals in the input.

Solution:

Here is the Python implementation of the above approach:

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

    i, n = 0, len(intervals)
    result = []

    # insert intervals before the new interval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1

    # merge overlapping intervals
    merged = newInterval
    while i < n and intervals[i][0] <= merged[1]:
        merged = [min(merged[0], intervals[i][0]), max(merged[1], intervals[i][1])]
        i += 1
    result.append(merged)

    # add the rest of the intervals
    while i < n:
        result.append(intervals[i])
        i += 1

    return result

The above solution is also available on my LeetCode account:

https://leetcode.com/submissions/detail/450431475/

Step by Step Implementation For Insert Interval

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public List insert(List intervals, Interval newInterval) {
        List result = new ArrayList();
        // check for empty list
        if(intervals == null || intervals.size() == 0) {
            result.add(newInterval);
            return result;
        }
        
        // insert newInterval at the correct position in the list
        boolean inserted = false;
        for(int i=0; i= curr.start) {
                // overlapping intervals, merge them
                Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
                prev = merged;
            } else {
                // non-overlapping intervals, add prev to result
                result.add(prev);
                prev = curr;
            }
        }
        // add the last interval
        result.add(prev);
        
        return result;
    }
}

# Definition for an interval.
# class Interval:
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution:
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        # insert newInterval at the correct position in intervals
        intervals.append(newInterval)
        intervals.sort(key=lambda x: x.start)
        
        # merge intervals
        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1].end < interval.start:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1].end = max(merged[-1].end, interval.end)

        return merged

/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
    
    // check for empty intervals 
    if (intervals.length === 0) { 
        intervals.push(newInterval); 
        return intervals; 
    } 
  
    // variables to keep track of index 
    // where interval needs to be inserted 
    // in the intervals array 
    let index = 0; 
  
    // traverse intervals array 
    for (let i = 0; i < intervals.length; i++) { 
        // if newInterval's start time is 
        // less than the current interval's start time 
        // insert newInterval at index 
        // and increment index 
        if (newInterval[0] < intervals[i][0]) { 
            index = i; 
            break; 
        } 
        // else if newInterval's start time lies 
        // in between the current interval's start and end time 
        // insert newInterval at index+1 
        // and increment index 
        else if (newInterval[0] >= intervals[i][0] && newInterval[0] <= intervals[i][1]) { 
            index = i + 1; 
            break; 
        } 
        // else if newInterval's start time is 
        // greater than the current interval's end time 
        // insert newInterval at index+1 
        // and increment index 
        else if (newInterval[0] > intervals[i][1]) { 
            index = i + 1; 
        } 
    } 
  
    // insert newInterval at index 
    intervals.splice(index, 0, newInterval); 
  
    // variable to store merged intervals 
    let mergedIntervals = []; 
  
    // push the first interval in the intervals array 
    // to the mergedIntervals array 
    mergedIntervals.push(intervals[0]); 
  
    // traverse intervals array 
    // starting from index 1 
    for (let i = 1; i < intervals.length; i++) { 
        // if the current interval's start time 
        // lies in between the previous interval's 
        // start and end time 
        // merge the current interval 
        // with the previous interval 
        if (intervals[i][0] <= mergedIntervals[mergedIntervals.length - 1][1]) { 
            mergedIntervals[mergedIntervals.length - 1][1] = Math.max(intervals[i][1], mergedIntervals[mergedIntervals.length - 1][1]); 
        } 
        // else there is no overlapping 
        // so push the current interval to the mergedIntervals array 
        else { 
            mergedIntervals.push(intervals[i]); 
        } 
    } 
  
    // return the mergedIntervals array 
    return mergedIntervals; 
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector insert(vector& intervals, Interval newInterval) {
        // edge case: empty intervals
        if (intervals.empty()) {
            intervals.push_back(newInterval);
            return intervals;
        }
        
        // find the position to insert
        int insertPos = 0;
        while (insertPos < intervals.size() && intervals[insertPos].start < newInterval.start) {
            insertPos++;
        }
        
        // insert the new interval
        intervals.insert(intervals.begin() + insertPos, newInterval);
        
        // merge intervals
        int i = 0;
        while (i < intervals.size() - 1) {
            // if current interval overlaps with next interval, merge the two
            if (intervals[i].end >= intervals[i + 1].start) {
                intervals[i].end = max(intervals[i].end, intervals[i + 1].end);
                intervals.erase(intervals.begin() + i + 1);
            }
            // otherwise move on to next interval
            else {
                i++;
            }
        }
        
        return intervals;
    }
};

/**
 * Definition for an interval.
 * public class Interval {
 *     public int start;
 *     public int end;
 *     public Interval() { start = 0; end = 0; }
 *     public Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public IList Insert(IList intervals, Interval newInterval) {
        //edge case: if intervals is null or empty, simply add newInterval to the list and return
        if(intervals == null || intervals.Count == 0){
            intervals.Add(newInterval);
            return intervals;
        }
        
        //find the position to insert newInterval
        int insertPos = 0;
        while(insertPos < intervals.Count && intervals[insertPos].start < newInterval.start){
            insertPos++;
        }
        
        //insert newInterval at the correct position
        intervals.Insert(insertPos, newInterval);
        
        //merge intervals if necessary
        return Merge(intervals);
    }
    
    //helper function to merge intervals if necessary
    private IList Merge(IList intervals){
        IList res = new List();
        
        //iterate through intervals
        foreach(Interval interval in intervals){
            //if res is empty or the current interval does not overlap with the last interval in res, simply add it to res
            if(res.Count == 0 || res[res.Count - 1].end < interval.start){
                res.Add(interval);
            }
            //otherwise, there is overlap, so update the end of the last interval in res to be the max of the end of the last interval in res and the end of the current interval
            else{
                res[res.Count - 1].end = Math.Max(res[res.Count - 1].end, interval.end);
            }
        }
        
        return res;
    }
}