Insert Interval

Medium

The problem

You get a list of time ranges [start, end], already sorted by start, where no two ranges overlap. Add one more range, newInterval, and return the full list, merging any ranges that overlap. Ranges that only touch at one point (like [1, 3] and [3, 5]) count as overlapping.

Example 1
Input: intervals = [[1, 3], [6, 9]], newInterval = [2, 5]
Output: [[1, 5], [6, 9]]
[2, 5] overlaps [1, 3], so they become [1, 5]. [6, 9] is untouched.
Example 2
Input: intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]
Output: [[1, 2], [3, 10], [12, 16]]
[4, 8] overlaps [3, 5], [6, 7] and [8, 10], and together they cover 3 to 10.
Example 3
Input: intervals = [[1, 2], [5, 6]], newInterval = [3, 4]
Output: [[1, 2], [3, 4], [5, 6]]
The new range overlaps nothing, so it just slots in between.

Limits

0 ≤ len(intervals) ≤ 100,000
start ≤ end for every range
The returned list must stay sorted by start

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

The list is sorted and non-overlapping. There are three phases: before the new one, overlapping it, after it.

The idea

Copy intervals ending before newStart; merge all overlapping ones (min start, max end); copy the rest.

Target: O(n) time

Go function shape

func insert(intervals [][]int, newInterval []int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Insert: insert newInterval into sorted, non-overlapping intervals and merge.
// No sorting needed: three phases — before, overlapping, after.
func Insert(intervals [][]int, newInterval []int) [][]int {
	out := [][]int{}
	i, n := 0, len(intervals)
	for i < n && intervals[i][1] < newInterval[0] { // entirely before
		out = append(out, intervals[i])
		i++
	}
	merged := []int{newInterval[0], newInterval[1]}
	for i < n && intervals[i][0] <= merged[1] { // overlaps: absorb
		merged[0] = min(merged[0], intervals[i][0])
		merged[1] = max(merged[1], intervals[i][1])
		i++
	}
	out = append(out, merged)
	for ; i < n; i++ { // entirely after
		out = append(out, intervals[i])
	}
	return out
}

Read the lesson: Intervals