Skip to main content

Insert Interval


Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). Return the resulting set of intervals.

Example 1



# Insert Interval Algorithm
# Given a set of non-overlapping intervals and a new interval,
# insert the new interval into the existing set such that the set remains non-overlapping

# Solution:
# We will use a greedy approach to solve this problem.
# We will use two pointers start and end to keep track of the start and end of the new interval.

# Step 1: We will iterate over the intervals,
# and check if the current interval overlaps with our new interval.
# If it does, we will update the start and end pointers accordingly.

def insert_interval(intervals, new_interval):
start, end = new_interval
result = []
for interval in intervals:
if interval[1] < start:
# no overlap
elif interval[0] > end:
# no overlap
# overlap
start = min(start, interval[0])
end = max(end, interval[1])

# add the new interval
result.append([start, end])
return sorted(result)