Insert Interval

Intuition

• Literally check out each case by hand
• To avoid issues, take the disjoint cases first (those cases where the target interval is not overlapping with the current interval and is thereby placed to the left or to the right)

Complexity

• Runtime: $O(N)$ to place each interval,
• Space: $O(N)$ for axillary array holding N elements

Code

Slightly Cleaned Up

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        target_start, target_end = newInterval
        appended = False
        for i, (cur_start, cur_end) in enumerate(intervals):
            if appended:
                res.extend(intervals[i:])
                break
 
            # Target disjoint to the left
            if (target_end < cur_start):
                res.append([target_start, target_end])
                res.append([cur_start, cur_end])
                appended = True
            # Target disjoint to the right
            elif (target_start > cur_end):
                res.append([cur_start, cur_end])
            # Overlapped but target to the left
            elif (target_start <= cur_start) and (target_end <= cur_end):
                res.append([target_start, cur_end])
                appended = True
            elif target_start >= cur_start:
                # Overlapped but target to the right
                if target_end > cur_end:
                    target_start = cur_start
                    target_end = target_end
                # Be consumed by
                else:
                    res.append([cur_start, cur_end])
                    appended = True
 
        if not appended:
            res.append([target_start, target_end])
 
        return res

Each Case Made Explicit

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        target_start, target_end = newInterval
        appended = False
        for i, (cur_start, cur_end) in enumerate(intervals):
            if appended:
                res.extend(intervals[i:])
                break
            # Be consumed by
            if (target_start >= cur_start) and (target_end <= cur_end):
                res.append([cur_start, cur_end])
                appended = True
            # Target disjoint to the left
            elif (target_end < cur_start):
                res.append([target_start, target_end])
                res.append([cur_start, cur_end])
                appended = True
            # Overlapped but target to the left
            elif (target_start <= cur_start) and (target_end <= cur_end):
                res.append([target_start, cur_end])
                appended = True
            # Target disjoint to the right
            elif (target_start > cur_end):
                res.append([cur_start, cur_end])
            # Overlapped but target to the right
            elif (target_start >= cur_start) and (target_end > cur_end):
                target_start = cur_start
                target_end = target_end
            else:
                print("HOUSTON")
 
        if not appended:
            res.append([target_start, target_end])
 
        return res

Notes

---

References

https://leetcode.com/problems/insert-interval/