{"id":977,"date":"2025-08-22T11:37:53","date_gmt":"2025-08-22T06:07:53","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=977"},"modified":"2025-08-22T11:37:55","modified_gmt":"2025-08-22T06:07:55","slug":"insert-interval","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/insert-interval\/","title":{"rendered":"Insert Interval | Leetcode 57 | Greedy Solution"},"content":{"rendered":"\n

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.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>: intervals = [[1,3],[6,9]], newInterval = [2,5]<\/span><\/span>\nOutput<\/span>: [[1,5],[6,9]]<\/span><\/span>\nExplanation<\/span>: [2,5] overlaps with [1,3], they merge into [1,5].<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]<\/span><\/span>\nOutput<\/span>: [[1,2],[3,10],[12,16]]<\/span><\/span>\nExplanation<\/span>: [4,8] overlaps with [3,5], [6,7], and [8,10] merging to [3,10].<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Goal: keep the output intervals sorted and non-overlapping after inserting the new segment.<\/p>\n\n\n\n
\n\n\n\n
Intuition and Approach (Optimal Greedy)<\/h2>\n\n\n\n
Because the input intervals are already sorted and non-overlapping, we can process them in three phases using a single pass.<\/p>\n\n\n\n
    \n
  1. Add all intervals that end before the new interval starts.
    These cannot overlap with the new interval, so append them as is.<\/li>\n\n\n\n
  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:\n