Insert Interval

Problem Statement

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 you need to insert into intervals such that the intervals in the resulting array remain non-overlapping and sorted.

Return the new list of intervals after the insertion.

Inserting at that position such that:

• Interval remain sorted.
• If overlapped merge it.

Examples

Example 1:

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

Explanation: The new interval [2,5] overlaps with [1,3], so they are merged to [1,5].

How we find the overlap?

         (2)---------------(5)

    (1)-----------(3)

In order to find overlaping,
For the starting point of the new interval we take the minimum from both's
starting point.
    new[0] = min(1, 2)
           = 1
For the end point of the new interval, we take the maximum from both's
end point.
    new[1] = max(5, 3)
           = 5

So the new interval is (1, 5)

Example 2:

Input; inteval = [], newInterval = [5, 7]
Output: [[5, 7]]

Explanation: As there are no intervals, just insert the new interval.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

• As stated in the problem that intervals are already sorted in ascending order, so we can use a simple linear scan to find the appropriate place to insert the new interval.
• We handle intervals in three groups:
  1. Non overlapping: Intervals that come before the new interval and don't overlap.
  2. Overlapping intervals: Intervals that overlap with the new interval and need to be merged.
  3. Non overlapping intervals: Intervals that come after the new interval and don't overlap (Remaining intervals after the merging of the new interval).

Approach:

1. Initialize an empty result array result.
2. Iterate through the intervals:
   • Before overlap: If the current interval's end is less than the new interval's start, add the current interval to result.
   • Merge: If the current interval overlaps with the new interval, merge them by adjusting the start and end of the new interval.
   • After overlap: If the current interval's start is greater than the new interval's end, add the new interval to the result and append all the remaining intervals.
3. Return the result.

Dry Run:

intervals = [
             [1, 2],
             [3, 5],
             [6, 7],
             [8, 10],
             [12, 16]
            ]
newInterval = [4, 8]

As stated in the problem that intervals are already sorted in ascending order.

First Phase (no overlap):

intervals = [
             [1, 2],
             [3, 5],
             [6, 7],
             [8, 10],
             [12, 16]
            ]

newInterval = [4, 8]

     1----2
               3---------5
                              6----7
                                        8--------10
                                                       11--------13
                        newInterval
                    4-------------------8

+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1    2    3    4    5    6    7    8    9    10   11   12   13


results = +--------+
          |        |
          +--------+

    Pick the first interval [1, 2], as it comes before the newInterval
    [4,  8]
    so we add it directly to the result.

Second Iteration (merge overlaps):

intervals = [
             [1, 2],
             [3, 5],
             [6, 7],
             [8, 10],
             [12, 16]
            ]

newInterval = [4, 8]

     1----2
               3---------5
                              6----7
                                        8--------10
                                                       11--------13
                        newInterval
                    4-------------------8

+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1    2    3    4    5    6    7    8    9    10   11   12   13


results = +--------+
          | [1, 2] |
          +--------+

    Interval [3, 5], it overlaps with the newInterval
    [4, 8] since (3 <= 4),
         Merge it by updating its end time as:
             max(5, 8) = 8
         Thus it becomes [3, 8]

   Interval [6, 7] also overlaps with [3, 8], so we
   further merge them into [3, 8] by doing same:
         Merge it by updating its end time as:
             max(7, 8) = 8
         Thus it becomes [3, 8] same.

   Interval [8, 10] also overlaps with [3, 8], so we
   merge it:
        Merge it by updating its end time as:
            max(10, 8) = 10
        Thus it becomes [3, 10].

   Interval [12, 16] is not overlapping so, stop here
   and push [3, 10] into the result.

Third Phase (no overlap - remaining elements):

intervals = [
             [1, 2],
             [3, 5],
             [6, 7],
             [8, 10],
             [12, 16]
            ]

newInterval = [4, 8]

     1----2
               3---------5
                              6----7
                                        8--------10
                                                       11--------13
                        newInterval
                    4-------------------8

+----+----+----+----+----+----+----+----+----+----+----+----+----+
0    1    2    3    4    5    6    7    8    9    10   11   12   13


results = +--------+
          | [1, 2] |
          +--------+
          | [3, 10]|
          +--------+

    Interval [12, 16] comes after the newInterval [3, 10],
    so add it to the result.

Final Result:

results = +--------+
          | [1, 2] |
          +--------+
          | [3, 10]|
          +--------+
          |[12, 16]|
          +--------+

Code:

class Solution {
public:
   vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int n = intervals.size(), i = 0;
        vector<vector<int>> res;
        
        
// Step 1: Add all intervals that come before the new interval (non-overlapping)
        //case 1: no overlapping case before the merge intervals
		//compare ending point of intervals to starting point of newInterval
        while(i < n && intervals[i][1] < newInterval[0]){
            res.push_back(intervals[i]);
            i++;
        }                           
		
		// Step 2: Merge overlapping intervals with new interval
		//case 2: overlapping case and merging of intervals
        while(i < n && newInterval[1] >= intervals[i][0]){
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval); // Add the merged interval.
        
        
// Step 3: Add all remaining intervals after the new interval.
        // case 3: no overlapping of intervals after newinterval being merged
        while(i < n){
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};

Complexity Analysis:

• Time Complexity:
  • O(n): We iterate over all intervals once, performing constant-time operations inside the loop.
• Space Complexity:
  • O(n): We use an output list to store the result, which can have up to n+1 intervals in the worst case.
  • We can ignore this as it is mentioned in the problem statement to return new list.