Insert Interval

LeetCode 57 | Difficulty: Medium

Medium

Problem Description

You are given an array of non-overlapping intervals intervals where intervals[i] = [start~i~, end~i~] represent the start and the end of the i^th interval and intervals is sorted in ascending order by start~i~. 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 start~i~ 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 <= 10^4`

- `intervals[i].length == 2`

- `0 <= start~i~ <= end~i~ <= 10^5`

- `intervals` is sorted by `start~i~` in **ascending** order.

- `newInterval.length == 2`

- `0 <= start <= end <= 10^5`

Topics: Array

---

Solutions

Solution 1: C# (Best: 140 ms)

Metric	Value
Runtime	140 ms
Memory	43.5 MB
Date	2021-12-25

Solution

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        List<int[]> result = new List<int[]>();
    foreach (var nextInterval in intervals)
    {
        if(newInterval == null || nextInterval[1] < newInterval[0])
        {
            result.Add(nextInterval);
        }
        else if(nextInterval[0] > newInterval[1])
        {
            result.Add(newInterval);
            result.Add(nextInterval);
            newInterval = null;
        }
        else
        {
            newInterval[0] = Math.Min(newInterval[0], nextInterval[0]);
            newInterval[1] = Math.Max(newInterval[1], nextInterval[1]);
        }

    }
    if(newInterval != null)
    {
        result.Add(newInterval);
    }
    
    return result.ToArray();
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Intervals Array is sorted. Can you use Binary Search to find the correct position to insert the new Interval.?

Hint 2: Can you try merging the overlapping intervals while inserting the new interval?

Hint 3: This can be done by comparing the end of the last interval with the start of the new interval and vice versa.