💬 Discord
Sign In
NeetCode #832LC-57MediumIntervalsBlind 75NC 150NC 250
← Back to All Problems

#832 · #57 · Insert Interval(插入区间)

📌 Problem Statement & Constraints

You are given an array of non-overlapping intervals intervals, sorted by start, and a newInterval. Insert newInterval and merge any overlaps so the result stays non-overlapping and sorted. Return the resulting array. Constraints: 0 <= intervals.length <= 10^4, 0 <= intervals[i][0] <= intervals[i][1] <= 10^5, 0 <= newInterval[0] <= newInterval[1] <= 10^5.

💡 Core Algorithmic Approaches

  1. The intervals are already sorted, so a single linear pass suffices -- no sort is needed.
  2. First copy every interval that ends before newInterval starts; these are untouched.
  3. Then absorb every interval that starts at or before the current newInterval end, widening newInterval to the union.
  4. Append the merged interval, then copy the untouched tail.

💻 Benchmark Python3 Implementation

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i = 0
        n = len(intervals)
        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])            # strictly before, no overlap
            i += 1
        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
        res.append(newInterval)
        res.extend(intervals[i:])
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): a single pass over the sorted intervals.
💾 Space Complexity
O(n) for the output (the algorithm uses O(1) extra).

⚠️ Interview Pitfalls & Follow-ups

  • Using <= for the before-test: touching intervals like [1,2] and [2,3] are considered overlapping, so the test must be strict end < newStart.
  • Sorting the input again: it is already sorted, and sorting would not help the merge.
  • Merging only one interval: the new interval can overlap a whole run, which is why the second loop keeps absorbing.
  • Forgetting the empty input: intervals may be empty; the loops simply do not execute and newInterval is appended alone.