# Insert Interval
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insert-interval)
Canonical: https://scaleengineer.com/dsa/problems/insert-interval
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Google](https://scaleengineer.com/companies/google), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [PhonePe](https://scaleengineer.com/companies/phonepe), [MongoDB](https://scaleengineer.com/companies/mongodb), [Tesco](https://scaleengineer.com/companies/tesco)
---
## Problem
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_.

**Note** that you don't need to modify `intervals` in-place. You can make a new array and return it.

**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].

**Constraints:**

* `0 <= intervals.length <= 104`
* `intervals[i].length == 2`
* `0 <= starti <= endi <= 105`
* `intervals` is sorted by `starti` in **ascending** order.
* `newInterval.length == 2`
* `0 <= start <= end <= 105`

# Approaches
## Brute Force with Sorting
This approach involves adding the new interval to the existing list of intervals and then treating it as a standard 'Merge Intervals' problem. The combined list is first sorted by the start times of the intervals, and then a linear scan is performed to merge any overlapping intervals.
**Time:** O(N log N), where N is the number of intervals. The sorting step dominates the time complexity. · **Space:** O(N), for storing the combined list of intervals and the final merged list, where N is the number of intervals in the input.
**Pros:** Conceptually simple, as it reduces the problem to a well-known one ('Merge Intervals').; Easy to implement if you already have a solution for merging intervals.
**Cons:** Inefficient because it doesn't utilize the pre-sorted nature of the input `intervals` array.; The sorting step `O(N log N)` is the bottleneck and is an unnecessary overhead.
### Explanation
The core idea is to simplify the problem by leveraging a known algorithm for merging intervals. First, we create a new list that contains all the intervals from the input `intervals` array plus the `newInterval`. This combined list is not guaranteed to be sorted or non-overlapping. We then sort this list based on the starting point of each interval. After sorting, we can iterate through the list and merge intervals. We initialize a result list with the first interval. Then, for each subsequent interval, we check if it overlaps with the last interval in our result list. If it overlaps, we merge them by updating the end point of the last interval in the result list. If it doesn't overlap, we simply add the current interval to the result list. Finally, we convert the result list back to a 2D array.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> allIntervals = new ArrayList<>(Arrays.asList(intervals));
        allIntervals.add(newInterval);

        // Sort the combined list by the start of each interval
        allIntervals.sort(Comparator.comparingInt(a -> a[0]));

        List<int[]> merged = new ArrayList<>();
        if (allIntervals.isEmpty()) {
            return new int[0][];
        }

        merged.add(allIntervals.get(0));

        for (int i = 1; i < allIntervals.size(); i++) {
            int[] current = allIntervals.get(i);
            int[] lastMerged = merged.get(merged.size() - 1);

            // Check for overlap
            if (current[0] <= lastMerged[1]) {
                // Merge by updating the end of the last merged interval
                lastMerged[1] = Math.max(lastMerged[1], current[1]);
            } else {
                // No overlap, add the current interval
                merged.add(current);
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}
```
### Algorithm
- Create a new `List<int[]>`.
- Add all intervals from the input `intervals` array to the list.
- Add `newInterval` to the list.
- Sort the list based on the start time of the intervals using a custom comparator.
- Initialize an empty `merged` list to store the final result.
- If the combined list is not empty, add the first interval to the `merged` list.
- Iterate through the sorted list from the second interval.
- For each interval, check if it overlaps with the last interval in the `merged` list (i.e., `current.start <= lastMerged.end`).
- If it overlaps, update the end of the last interval in `merged` to be the maximum of the two end times: `lastMerged.end = max(lastMerged.end, current.end)`.
- If it does not overlap, add the current interval to the `merged` list.
- Convert the `merged` list to a 2D array and return it.

## Single Pass Linear Scan
A more efficient approach is to iterate through the sorted `intervals` array just once, taking advantage of its sorted property. We can build the result list by handling three distinct cases in a single pass: intervals that come before the new interval, intervals that overlap with it, and intervals that come after it.
**Time:** O(N), where N is the number of intervals, as we iterate through the list only once. · **Space:** O(N), for storing the result list. In the worst case, the result has N+1 intervals.
**Pros:** Highly efficient with a linear time complexity.; Effectively uses the pre-sorted property of the input array, avoiding a costly re-sort.; Requires only a single pass through the data.
**Cons:** The logic is slightly more complex than the brute-force approach, involving multiple conditions and loops to handle the three distinct phases.
### Explanation
This approach avoids re-sorting and processes the intervals in a single linear scan. We iterate through the intervals and divide the process into three parts.

**Part 1: Add non-overlapping intervals from the beginning.** We iterate through the `intervals` array and add all intervals that end before `newInterval` starts to our result list. These intervals are guaranteed not to overlap with `newInterval` or any subsequent intervals.

**Part 2: Merge overlapping intervals.** We continue iterating through the `intervals` array. For all intervals that overlap with `newInterval` (i.e., their start is less than or equal to `newInterval`'s end), we merge them into `newInterval`. This is done by repeatedly updating `newInterval`'s start to the minimum of the current starts and its end to the maximum of the current ends.

**Part 3: Add the merged interval and remaining intervals.** After the merging loop, the `newInterval` now represents the combination of the original `newInterval` and all intervals it overlapped with. We add this merged `newInterval` to the result list. Then, we add all the remaining intervals from the input array to the result list. These are guaranteed to start after the merged `newInterval` ends.

Finally, we convert the result list to a 2D array.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;

        // 1. Add all intervals that end before newInterval starts
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }

        // 2. Merge all overlapping intervals with newInterval
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        // Add the merged interval
        result.add(newInterval);

        // 3. Add all remaining intervals
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }

        return result.toArray(new int[result.size()][]);
    }
}
```
### Algorithm
- Initialize an empty `result` list and an index `i = 0`.
- **Phase 1: Add non-overlapping intervals from the beginning.** Iterate through `intervals` while the current interval's end is less than `newInterval`'s start (`intervals[i][1] < newInterval[0]`). Add these intervals to `result`.
- **Phase 2: Merge overlapping intervals.** Iterate through `intervals` while the current interval's start is less than or equal to `newInterval`'s end (`intervals[i][0] <= newInterval[1]`). In each step, merge the current interval into `newInterval` by updating `newInterval`'s start and end: `newInterval[0] = min(newInterval[0], intervals[i][0])` and `newInterval[1] = max(newInterval[1], intervals[i][1])`.
- After the merging loop, add the final, merged `newInterval` to the `result` list.
- **Phase 3: Add remaining intervals.** Add all remaining intervals from the input array (from the current position of `i` to the end) to the `result` list.
- Convert the `result` list to a 2D array and return it.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        var ans = new List < int[] > ();
        int st = newInterval[0], ed = newInterval[1];
        bool insert = false;
        foreach(var interval in intervals) {
            int s = interval[0], e = interval[1];
            if (ed < s) {
                if (!insert) {
                    ans.Add(new int[] {
                        st,
                        ed
                    });
                    insert = true;
                }
                ans.Add(interval);
            } else if (st > e) {
                ans.Add(interval);
            } else {
                st = Math.Min(st, s);
                ed = Math.Max(ed, e);
            }
        }
        if (!insert) {
            ans.Add(new int[] {
                st,
                ed
            });
        }
        return ans.ToArray();
    }
}
```

### Java

```java
class Solution {
public
  int[][] insert(int[][] intervals, int[] newInterval) {
    int[][] newIntervals = new int[intervals.length + 1][2];
    for (int i = 0; i < intervals.length; ++i) {
      newIntervals[i] = intervals[i];
    }
    newIntervals[intervals.length] = newInterval;
    return merge(newIntervals);
  }
private
  int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b)->a[0] - b[0]);
    List<int[]> ans = new ArrayList<>();
    ans.add(intervals[0]);
    for (int i = 1; i < intervals.length; ++i) {
      int s = intervals[i][0], e = intervals[i][1];
      if (ans.get(ans.size() - 1)[1] < s) {
        ans.add(intervals[i]);
      } else {
        ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e);
      }
    }
    return ans.toArray(new int[ans.size()][]);
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> insert(vector<vector<int>> &intervals,
                             vector<int> &newInterval) {
    intervals.emplace_back(newInterval);
    return merge(intervals);
  }
  vector<vector<int>> merge(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> ans;
    ans.emplace_back(intervals[0]);
    for (int i = 1; i < intervals.size(); ++i) {
      if (ans.back()[1] < intervals[i][0]) {
        ans.emplace_back(intervals[i]);
      } else {
        ans.back()[1] = max(ans.back()[1], intervals[i][1]);
      }
    }
    return ans;
  }
};

```

### Python

```python
''' >>> a = [1,2,3,4,5] >>> a[1] 2 >>> a[~1] 4 ''' class Solution : def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ]) -> List [ List [ int ]]: start = newInterval [ 0 ] end = newInterval [ 1 ] left = list ( filter ( lambda x : x [ 1 ] < start , intervals )) # cast via list() right = list ( filter ( lambda x : x [ 0 ] > end , intervals )) if left + right != intervals : start = min ( start , intervals [ len ( left )][ 0 ]) # note, left not -1, because index starts at 0 end = max ( end , intervals [ ~ len ( right )][ 1 ]) # same, starting at right with index=0 return left + [[ start , end ]] + right ###### class Solution : # re-use Leetcode-56's merge solution def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ]) -> List [ List [ int ]]: intervals . append ( newInterval ) return self . merge ( intervals ) def merge ( self , intervals : List [ List [ int ]]) -> List [ List [ int ]]: ans = [] for intv in sorted ( intervals , key = lambda x : x [ 0 ]): if ans and ans [ - 1 ][ 1 ] >= intv [ 0 ]: ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], intv [ 1 ]) else : ans . append ( intv ) return ans ###### class Solution : def insert ( self , intervals : List [ List [ int ]], newInterval : List [ int ] ) -> List [ List [ int ]]: def merge ( intervals : List [ List [ int ]]) -> List [ List [ int ]]: intervals . sort () ans = [ intervals [ 0 ]] for s , e in intervals [ 1 :]: if ans [ - 1 ][ 1 ] < s : ans . append ([ s , e ]) else : ans [ - 1 ][ 1 ] = max ( ans [ - 1 ][ 1 ], e ) return ans intervals . append ( newInterval ) return merge ( intervals )
```