Insert Interval | Leetcode 57 | Greedy Solution

You are given a list of non-overlapping intervals sorted by start time, and a new interval to insert. Your task is to insert the new interval into the list so that the list remains sorted and non-overlapping by merging intervals when necessary. Return the resulting list.

Here’s the [Problem Link] to begin with.

Example 1

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Explanation: [2,5] overlaps with [1,3], they merge into [1,5].

Example 2

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: [4,8] overlaps with [3,5], [6,7], and [8,10] merging to [3,10].

Goal: keep the output intervals sorted and non-overlapping after inserting the new segment.

Intuition and Approach (Optimal Greedy)

Because the input intervals are already sorted and non-overlapping, we can process them in three phases using a single pass.

1. Add all intervals that end before the new interval starts.
   These cannot overlap with the new interval, so append them as is.
2. Merge all intervals that overlap with the new interval.
   While the current interval starts at or before the new interval ends, expand the new interval to cover the union by updating:
   • new.start = min(new.start, curr.start)
   • new.end = max(new.end, curr.end)
3. Append the merged new interval, then append the remaining intervals.
   Any remaining intervals start strictly after the merged interval and do not overlap.

This greedy sweep maintains order and merges exactly the intervals that overlap with the new one.

Code Implementation

Your provided optimal greedy solution with explanatory comments only:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i = 0
        n = len(intervals)

        # 1) Add all intervals that end before the new interval starts
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1
        
        # 2) Merge all intervals that overlap with newInterval
        while i < n and intervals[i][0] <= newInterval[1]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        
        # Add the merged interval
        res.append(newInterval)

        # 3) Append the remaining intervals
        while i < n:
            res.append(intervals[i])
            i += 1

        return res

Code explanation

• The first loop copies all intervals strictly to the left of newInterval (current interval end < new start). They do not overlap, so they are safe to append directly.
• The second loop processes all intervals that overlap with newInterval (current interval start ≤ new end). The new interval is expanded to cover the union of all overlaps.
• After merging, the expanded newInterval is appended.
• Finally, any intervals starting after the merged interval are appended as they are.

This logic relies on the original list being sorted by start time and non-overlapping, which ensures that all potential overlaps appear contiguously around the insertion point.

Time and Space Complexity

• Precise
  • Each interval is visited at most once across the three phases, so the total pass is O(n).
  • The result list holds all intervals plus the merged one, and we use only a few variables, so extra space is O(1) beyond the output list.
• Simplified
  • O(n) time and O(1) extra space (not counting the output).

Conclusion

By leveraging the sorted, non-overlapping property, a single greedy sweep cleanly inserts and merges the new interval. The algorithm is linear time, constant extra space, and straightforward to implement, making it the preferred solution for production and interviews.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.