Insert Interval
Problem Statement
You are given an array of non-overlapping intervals intervals
where intervals[i] = [start_i, end_i]
represents the start and the end time of the ith
interval. intervals
is initially sorted in ascending order by start_i
.
You are given another interval newInterval = [start, end]
.
Insert newInterval
into intervals
such that intervals
is still sorted in ascending order by start_i
and also intervals
still does not have any overlapping intervals. You may merge the overlapping intervals if needed.
Return intervals
after adding newInterval
.
Note: Intervals are non-overlapping if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.
Example 1:
Input: intervals = [[1,3],[4,6]], newInterval = [2,5]
Output: [[1,6]]
Example 2:
Input: intervals = [[1,2],[3,5],[9,10]], newInterval = [6,7]
Output: [[1,2],[3,5],[6,7],[9,10]]
Constraints:
0 <= intervals.length <= 1000
newInterval.length == intervals[i].length == 2
0 <= start <= end <= 1000
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(1)
space.
Hint 1
Iterate through the intervals and compare the new interval with each existing interval.
Hint 2
Consider three cases: the new interval is completely before, completely after, or overlapping with the current interval.
Hint 3
Merge overlapping intervals as needed.
Solution
Linear Search
def insert(intervals: list[list[int]], new_interval: list[int]) -> list[list[int]]: n = len(intervals) i = 0 res = []
while i < n and intervals[i][1] < new_interval[0]: res.append(intervals[i]) i += 1
while i < n and new_interval[1] >= intervals[i][0]: new_interval[0] = min(new_interval[0], intervals[i][0]) new_interval[1] = max(new_interval[1], intervals[i][1]) i += 1 res.append(new_interval)
while i < n: res.append(intervals[i]) i += 1
return res
Time complexity: O(n)
Space complexity: O(n)