Insert Interval - Miscellaneous / Interval

https://algo.monster/problems/insert_interval

Since the intervals are already sorted, we should take advantage of that and come up with a solution that runs in O(n) Instead of O(nlogn) (sorting). We can simply skip all the intervals that are before the new one, then merge all the intervals that overlap with the new one and then add the remaining intervals

I think the last solution fails on the test case:
intervals = [[1,2],[3,4],[6,7],[8,10],[12,16], [4.1, 5], [7.1, 7.5]]
new_interval = [4, 4.5]
the solution outputs [[1, 2], [3, 4.5], [6, 7], [8, 10], [12, 16], [4.1, 5], [7.1, 7.5]], but it’s still overlapping.

Indeed. Good references here:
https://leetcode.com/problems/insert-interval/

Test cases here don’t cover much. Absolutely have to test on https://leetcode.com/problems/insert-interval

O(log n) + two pointers solution:

def insert_interval(intervals: List[List[int]], new_interval: List[int]) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE

left_idxs = [x[0] for x in intervals]
idx = bisect_right(left_idxs, new_interval[0])

intervals.insert(idx, new_interval)

right = idx + 1
left = idx - 1

# merge to the right
while idx + 1 < len(intervals) and has_overlap(intervals[idx], intervals[idx + 1]):
    __next = intervals.pop(idx + 1)
    intervals[idx] = [
        min(intervals[idx][0], __next[0]),
        max(intervals[idx][1], __next[1]),
    ]

while idx - 1 >= 0 and has_overlap(intervals[idx - 1], intervals[idx]):
    __previous = intervals.pop(idx - 1)
    idx -= 1
    intervals[idx] = [
        min(intervals[idx][0], __previous[0]),
        max(intervals[idx][1], __previous[1]),
    ]

return intervals

My solution in O(N). Simple loop through the intervals.

def insert_interval(intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
    
    before = []
    after = []
    
    for interval in intervals:
        
        if interval[1] < new_interval[0]: 
            before.append(interval)
            
        elif interval[0] > new_interval[1]:
            after.append(interval)
                
        else:
            new_interval[0] = min(new_interval[0], interval[0])
            new_interval[1] = max(new_interval[1], interval[1])
    
    res = before + [new_interval] + after        
    return res