mediumIntervals

Insert Interval

Insert an interval into a list of disjoint sorted closed intervals, merging any overlap, including shared endpoints.

Work through the cases

3 examples

Input notation

New interval start end on line 1; existing intervals on later lines, in increasing start order. There may be no existing intervals.

Expected result

Merged intervals as start end, one per line.

Case 1

Input

2 5
1 3
6 9

Expected output

1 5
6 9

Case 2

Input

Expected output

1 2
3 10

Case 3

Input

1 2

Expected output

1 2

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

The first idea is to insert newInterval into the list and reuse ordinary interval merging. n ≤ 10^4, so an O(n log n) sort will pass. The list is already sorted and non-overlapping, but reusing merge-intervals is the least extra code: append, sort, merge. Correct; it just ignores the given order.

We can first add the new interval newInterval to the interval list intervals, and then merge according to the regular method of interval merging.

The time complexity is O(n × log n), and the space complexity is O(n). Here, n is the number of intervals.

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[][] newIntervals = new int[intervals.length + 1][2];
        for (int i = 0; i < intervals.length; ++i) {
            newIntervals[i] = intervals[i];
        }
        newIntervals[intervals.length] = newInterval;
        return merge(newIntervals);
    }

    private int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; ++i) {
            int s = intervals[i][0], e = intervals[i][1];
            if (ans.get(ans.size() - 1)[1] < s) {
                ans.add(intervals[i]);
            } else {
                ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], e);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.