class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
"""
Inserts a new interval into a list of non-overlapping sorted intervals, merging if necessary.
Parameters:
intervals (List[List[int]]): A list of sorted, non-overlapping intervals [start, end].
newInterval (List[int]): The new interval to add.
Returns:
List[List[int]]: The resulting list of merged intervals after inserting newInterval.
"""
merged = [] # This list will store the resulting intervals.
i, n = 0, len(intervals)
# Add all intervals ending before the new interval starts.
while i < n and intervals[i][1] < newInterval[0]:
merged.append(intervals[i])
i += 1
# Merge overlapping intervals with newInterval.
while i < n and intervals[i][0] <= newInterval[1]:
# Update the newInterval's start to the minimum, and end to the maximum.
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
# Append the merged newInterval.
merged.append(newInterval)
# Add the remaining intervals (those starting after the newInterval ends).
while i < n:
merged.append(intervals[i])
i += 1
return merged
Summary of Techniques and Approaches:
Two-Phase Iteration: The solution breaks down the problem into distinct phases—first handling non-overlapping intervals before the new interval, then merging any overlapping intervals, and finally appending the remaining intervals. This separation simplifies reasoning about different cases.
In-Place Merging: By updating the new interval in place with the minimum start and maximum end during overlapping, the solution avoids unnecessary extra space and operations. This approach is beneficial for problems requiring interval merging or dynamic range adjustments.
Efficient Iteration and Conditional Checks: The algorithm ensures that each interval is processed only once, leading to an optimal time complexity of O(n). Recognizing how to efficiently traverse sorted data with condition-based branches is a crucial technique for many algorithmic challenges.
General Application: These strategies can be applied to a variety of problems including interval scheduling, merging overlapping ranges, and sliding window problems. When encountering a sorted dataset that requires conditional processing or merging, consider breaking the problem into distinct phases to simplify the logic and improve performance.