Insert Interval

Problem statement

You are given a list of non-overlapping intervals already sorted by start time, plus one new interval. Insert the new interval into the list and merge anything that now overlaps, so the result stays sorted and non-overlapping.

Example:

Input:

intervals = [[1, 3], [6, 9]], newInterval = [2, 5]

Expected output:

[[1, 5], [6, 9]]

Why: [1, 3] and [2, 5] merge into [1, 5].

Practice on LeetCode: Insert Interval

Golang Solution

Binary-search for the first interval whose start is not less than newInterval[0], splice the new interval in at that index, then walk once to merge any overlapping neighbors (same fold as Merge Intervals).

Time: O(n) — the merge walk is linear; binary search is O(log n)
Space: O(n) — for the result slice

func insert(intervals [][]int, newInterval []int) [][]int {
    low, high := 0, len(intervals)-1

    for low <= high {
        mid := low + (high - low) / 2
        if intervals[mid][0] < newInterval[0] {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }

    result := make([][]int, 0)
    result = append(result, intervals[:low]...)
    result = append(result, newInterval)
    result = append(result, intervals[low:]...)

    last := 0
    for i := 1; i < len(result); i++ {
        if result[last][1] >= result[i][0] {
            result[last][1] = max(result[last][1], result[i][1])
        } else {
            last++
            result[last] = result[i]
        }
    }

    return result[:last+1]
}