Insert Interval

Problem Summary

• Given an already sorted list with non-overlapping intervals
• Insert the given new interval
• Ensure your output has no overlapping intervals and is sorted

What is Being Asked?

• Insert an interval
• Merge overlapping intervals if any

Key Observations

• Already sorted so solve it in $O(n)$
• Cannot just insert and run sort + merge algorithm from Merge Intervals

Approach Taken

• Insert the new interval to its appropriate spot first based on the start time. Three possible options:
  • insert at the first item
  • insert anywhere in the middle
  • insert at the end
• Merge all overlapping intervals like Merge Intervals

Why This Works

• Intervals remain sorted by start time if the new interval is inserted at the right spot
• Merging overlapping intervals is just $O(n)$

Main Concepts Used

• Intervals

Time & Space Complexity

• Time: $O(n)$ → Reason: Potentially all intervals may be merged
• Space: $O(n)$ → Reason: Result array

Code

class Solution:
    def insert(
        self, intervals: List[List[int]], newInterval: List[int]
    ) -> List[List[int]]:
        if not intervals:
            return [newInterval]

        newStart, newEnd = newInterval
        isInserted = False
        for i, (curStart, curEnd) in enumerate(intervals):
            if newStart <= curStart:
                intervals.insert(i, newInterval)
                isInserted = True
                break
        if not isInserted: # insert at the end
            intervals.append(newInterval)

        result = []
        prev = None
        for curStart, curEnd in intervals:
            if not prev:
                prev = [curStart, curEnd]
                continue

            prevStart, prevEnd = prev
            if curStart <= prevEnd:
                prev = [prevStart, max(prevEnd, curEnd)]
            else:
                result.append(prev)
                prev = [curStart, curEnd]
        if prev:
            result.append(prev)

        return result

Common Mistakes / Things I Got Stuck On

• Not being able to come up with the high level algorithm on how to insert the new interval