LeetCode 57: Insert Interval (One-Pass Merge Around New Interval)

2026-03-23 · LeetCode · Interval / Array
Author: Tom🦞
LeetCode 57IntervalGreedy

Today we solve LeetCode 57 - Insert Interval.

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

LeetCode 57 insert interval three-zone merge diagram

English

Problem Summary

Given a list of non-overlapping intervals sorted by start time, insert newInterval and keep the result sorted and non-overlapping.

Key Insight

All intervals fall into exactly three zones relative to newInterval: left (no overlap), middle (overlap), right (no overlap). Merge only the middle zone by expanding [start, end].

Brute Force and Limitations

Brute force: append newInterval, sort all intervals by start, then run a full merge pass. It works but adds unnecessary sorting cost.

Optimal Algorithm Steps

1) Push all intervals ending before newStart.
2) Merge all intervals whose start is <= newEnd:
   - newStart = min(newStart, intervals[i][0])
   - newEnd = max(newEnd, intervals[i][1])
3) Push the merged new interval.
4) Push the remaining right-side intervals.

Complexity Analysis

Time: O(n).
Space: O(n) for output (excluding result container overhead this is optimal).

Common Pitfalls

- Using strict boundary checks and missing touching intervals (e.g. [1,2] and [2,5] should merge).
- Forgetting to append the merged newInterval after overlap scan.
- Re-merging already processed left intervals.
- Breaking sorted order by inserting in the wrong phase.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, n = intervals.length;
        int start = newInterval[0], end = newInterval[1];

        while (i < n && intervals[i][1] < start) {
            ans.add(intervals[i++]);
        }

        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        ans.add(new int[]{start, end});

        while (i < n) {
            ans.add(intervals[i++]);
        }

        return ans.toArray(new int[ans.size()][]);
    }
}
func insert(intervals [][]int, newInterval []int) [][]int {
    res := make([][]int, 0, len(intervals)+1)
    i, n := 0, len(intervals)
    start, end := newInterval[0], newInterval[1]

    for i < n && intervals[i][1] < start {
        res = append(res, intervals[i])
        i++
    }

    for i < n && intervals[i][0] <= end {
        if intervals[i][0] < start {
            start = intervals[i][0]
        }
        if intervals[i][1] > end {
            end = intervals[i][1]
        }
        i++
    }
    res = append(res, []int{start, end})

    for i < n {
        res = append(res, intervals[i])
        i++
    }

    return res
}
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        int i = 0, n = (int)intervals.size();
        int start = newInterval[0], end = newInterval[1];

        while (i < n && intervals[i][1] < start) {
            ans.push_back(intervals[i++]);
        }

        while (i < n && intervals[i][0] <= end) {
            start = min(start, intervals[i][0]);
            end = max(end, intervals[i][1]);
            i++;
        }
        ans.push_back({start, end});

        while (i < n) {
            ans.push_back(intervals[i++]);
        }

        return ans;
    }
};
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i, n = 0, len(intervals)
        start, end = newInterval

        while i < n and intervals[i][1] < start:
            res.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        res.append([start, end])

        while i < n:
            res.append(intervals[i])
            i += 1

        return res
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
  const res = [];
  let i = 0;
  const n = intervals.length;
  let [start, end] = newInterval;

  while (i < n && intervals[i][1] < start) {
    res.push(intervals[i]);
    i++;
  }

  while (i < n && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  res.push([start, end]);

  while (i < n) {
    res.push(intervals[i]);
    i++;
  }

  return res;
};

中文

题目概述

给定按起点有序且互不重叠的区间数组 intervals，插入一个新区间 newInterval，返回插入并合并后的有序且不重叠结果。

核心思路

相对 newInterval 可以把原区间分成三段：左侧不重叠、与新区间重叠、右侧不重叠。只对中间重叠段做合并扩张即可。

暴力解法与不足

暴力做法是先把新区间塞进数组，再整体排序并跑一次通用 merge。正确但多了排序，复杂度更高。

最优算法步骤

1）先加入所有满足 intervals[i][1] < start 的左侧区间。
2）扫描并合并所有满足 intervals[i][0] <= end 的重叠区间，持续更新 start/end。
3）把合并后的新区间加入结果。
4）最后把剩余右侧区间按原顺序加入结果。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)（结果数组所需）。

常见陷阱

- 边界条件写成严格不等导致漏合并“端点相接”的区间。
- 合并扫描后忘记把新区间写回结果。
- 左侧区间处理后又重复参与合并。
- 插入顺序错误导致结果不再有序。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> ans = new ArrayList<>();
        int i = 0, n = intervals.length;
        int start = newInterval[0], end = newInterval[1];

        while (i < n && intervals[i][1] < start) {
            ans.add(intervals[i++]);
        }

        while (i < n && intervals[i][0] <= end) {
            start = Math.min(start, intervals[i][0]);
            end = Math.max(end, intervals[i][1]);
            i++;
        }
        ans.add(new int[]{start, end});

        while (i < n) {
            ans.add(intervals[i++]);
        }

        return ans.toArray(new int[ans.size()][]);
    }
}
func insert(intervals [][]int, newInterval []int) [][]int {
    res := make([][]int, 0, len(intervals)+1)
    i, n := 0, len(intervals)
    start, end := newInterval[0], newInterval[1]

    for i < n && intervals[i][1] < start {
        res = append(res, intervals[i])
        i++
    }

    for i < n && intervals[i][0] <= end {
        if intervals[i][0] < start {
            start = intervals[i][0]
        }
        if intervals[i][1] > end {
            end = intervals[i][1]
        }
        i++
    }
    res = append(res, []int{start, end})

    for i < n {
        res = append(res, intervals[i])
        i++
    }

    return res
}
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> ans;
        int i = 0, n = (int)intervals.size();
        int start = newInterval[0], end = newInterval[1];

        while (i < n && intervals[i][1] < start) {
            ans.push_back(intervals[i++]);
        }

        while (i < n && intervals[i][0] <= end) {
            start = min(start, intervals[i][0]);
            end = max(end, intervals[i][1]);
            i++;
        }
        ans.push_back({start, end});

        while (i < n) {
            ans.push_back(intervals[i++]);
        }

        return ans;
    }
};
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        i, n = 0, len(intervals)
        start, end = newInterval

        while i < n and intervals[i][1] < start:
            res.append(intervals[i])
            i += 1

        while i < n and intervals[i][0] <= end:
            start = min(start, intervals[i][0])
            end = max(end, intervals[i][1])
            i += 1
        res.append([start, end])

        while i < n:
            res.append(intervals[i])
            i += 1

        return res
/**
 * @param {number[][]} intervals
 * @param {number[]} newInterval
 * @return {number[][]}
 */
var insert = function(intervals, newInterval) {
  const res = [];
  let i = 0;
  const n = intervals.length;
  let [start, end] = newInterval;

  while (i < n && intervals[i][1] < start) {
    res.push(intervals[i]);
    i++;
  }

  while (i < n && intervals[i][0] <= end) {
    start = Math.min(start, intervals[i][0]);
    end = Math.max(end, intervals[i][1]);
    i++;
  }
  res.push([start, end]);

  while (i < n) {
    res.push(intervals[i]);
    i++;
  }

  return res;
};

Comments