Insert Interval
Medium
Array
Intervals
You are given an array of non-overlapping intervals `intervals` where `intervals[i] = [startᵢ, endᵢ]` represent the start and the end of the `i`th interval and `intervals` is sorted in ascending order by `startᵢ`. You are also given an interval `newInterval = [start, end]`. Insert `newInterval` into `intervals` such that `intervals` is still sorted in ascending order by `startᵢ` and `intervals` still does not have any overlapping intervals (merge overlapping intervals if necessary). Return `intervals` *after the insertion*.
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]]

Constraints

  • •0 <= intervals.length <= 10⁴
  • •intervals[i].length == 2
  • •0 <= startᵢ <= endᵢ <= 10⁵
  • •intervals is sorted by startᵢ in ascending order.
  • •newInterval.length == 2
  • •0 <= start <= end <= 10⁵
Time Complexity
O(n)
Space Complexity
O(n)
14
Case 1
Input: [[1,3],[6,9]] [2,5]
Expected: [[1,5],[6,9]]
Case 2
Input: [[1,2],[3,5],[6,7],[8,10],[12,16]] [4,8]
Expected: [[1,2],[3,10],[12,16]]
Case 3
Input: [] [5,7]
Expected: [[5,7]]