Insert Interval

Approach 1: Linear Search

• Uses a count i with i < n condition to avoid out of bound issue.
• A clear distinction between no overlapping and overlapping
• Merging intervals, not the most efficient, but it gets the job done without going into details.

n = len(intervals)
new_start, new_end = new_interval
i = 0
res = []
 
# Case 1: No overlapping before merging intervals
while i < n and intervals[i][1] < new_start:
    res.append(intervals[i])
    i += 1
 
# Case 2: Overlapping and merging intervals
while i < n and new_end >= intervals[i][0]:
    new_start = min(new_start, intervals[i][0])
    new_end = max(new_end, intervals[i][1])
    i += 1
res.append((new_start, new_end))
 
# Case 3: No overlapping after merging newInterval
while i < n:
    res.append(intervals[i])
    i += 1
 
return res