Skip to content

57. Insert Interval

Summary

Solution Approach Explanation (1-minute) Time Complexity Space Complexity
Linear Scan Iterate through intervals. Handle 3 cases: (1) new interval is completely before current - add new interval and remaining intervals; (2) new interval is completely after current - add current interval to result; (3) overlapping intervals - merge by taking min start and max end, continue merging until no overlap. O(n) O(n)

Implementation

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        output = []

        for i, interval in enumerate(intervals):
            curr_start, curr_end = interval
            new_start, new_end = newInterval
            # Case 1: new interval is all the way to the left
            if new_end < curr_start:
                output.append(newInterval)
                output += intervals[i:]
                return output
            # Case 2: new interval is all the way to the right
            elif curr_end < new_start:
                output.append(interval)
            # Case 3: overlapping
            else:
                newInterval = [
                    min(new_start, curr_start),
                    max(new_end, curr_end)
                ]

        output.append(newInterval)

        return output