def insert_interval(intervals, new_interval):
result = []
i = 0
n = len(intervals)
# 1. Add all intervals that end BEFORE the new interval starts.
# These cannot overlap.
while i < n and intervals[i][1] < new_interval[0]:
result.append(intervals[i])
i += 1
# 2. Merge all intervals that DO overlap with the new interval.
# Overlap condition: intervals[i].start <= new_interval.end
while i < n and intervals[i][0] <= new_interval[1]:
new_interval[0] = min(new_interval[0], intervals[i][0])
new_interval[1] = max(new_interval[1], intervals[i][1])
i += 1
# Add the merged interval
result.append(new_interval)
# 3. Add all remaining intervals (those starting AFTER new interval ends)
while i < n:
result.append(intervals[i])
i += 1
return result
def main():
intervals = [[1, 3], [6, 8], [13, 18]]
new_interval1 = [9, 11]
updated = insert_interval(intervals, new_interval1)
new_interval2 = [2, 5]
updated = insert_interval(updated, new_interval2)
print("Updated intervals:")
for iv in updated:
print(f"[{iv[0]},{iv[1]}]", end=" ")
print()
if __name__ == "__main__":
main()
"""
run:
Updated intervals:
[1,5] [6,8] [9,11] [13,18]
"""
