Insert Interval
- 2 min read
- Interval
- LC-Medium
3 years ago
Solution
- Maintain a list called
answhich is your answer. Initially, it is an empty list. - We will iterate through the intervals one by one. At each iteration, there are 3 possible cases to consider:
- If a new interval ends before the current interval, append new interval to answer and append remaining intervals to answer.
- We return immediately since our new interval has found a valid position
- We check for this by checking if
newInterval[1] < intervals[i][0]
- If the new interval comes after the current interval, append current interval, and move to next iteration.
- We don't append new interval yet because it might overlap with any of the remaining intervals.
- If there's an overlap between intervals, combine both intervals by considering new intervals start and end and minimum and maximum of start and end of current interval and new interval respectively.
- Like the first case, we don't append the new interval yet, because there might be any other intervals we need to merge the new interval with.
- If a new interval ends before the current interval, append new interval to answer and append remaining intervals to answer.
- At the end, the new interval still might not be merged, so we need to add it to the answer.
- It's basically the same as our first case, but since the while loop might have concluded before that code could be reached, we need to do the same thing again at the end.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
ans = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]:
ans.append(newInterval)
return ans + intervals[i:]
elif newInterval[0] > intervals[i][1]:
ans.append(intervals[i])
else:
newInterval = [min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])]
ans.append(newInterval)
return ans