Merge Intervals

Interval problems typically start with sorting by start time, then scanning left to right to merge, insert, or count overlaps.

Use when: you’re working with time ranges, schedules, or any overlapping segments.

Merge overlapping intervals. After sorting by start time, two intervals overlap if the current start is <= the previous end.

Sort by start time.

If merged is empty or no overlap with the last merged interval, just append.

Overlap: extend the end of the last interval.

Insert a new interval into a sorted, non-overlapping list. This shows the three-phase pattern: before, overlapping, after.

Phase 1: add all intervals that end before new starts.

Phase 2: merge all overlapping intervals with new.

Phase 3: add remaining intervals.

Trace: merge [1,3, [2,6], [8,10], [15,18]]

After sort: [1,3, [2,6], [8,10], [15,18]]

[2,6]: overlap (2 <= 3), extend -> [[1,6]] [8,10]: no overlap (8 > 6), append -> [[1,6],[8,10]] [15,18]: no overlap, append -> [[1,6],[8,10],[15,18]]

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	var merged [][]int

	for _, interval := range intervals {
		if len(merged) == 0 || merged[len(merged)-1][1] < interval[0] {
			merged = append(merged, interval)
		} else {
			last := merged[len(merged)-1]
			if interval[1] > last[1] {
				last[1] = interval[1]
			}
		}
	}

	return merged
}
func insert(intervals [][]int, newInterval []int) [][]int {
	var result [][]int
	i := 0
	for i < len(intervals) && intervals[i][1] < newInterval[0] {
		result = append(result, intervals[i])
		i++
	}
	for i < len(intervals) && intervals[i][0] <= newInterval[1] {
		if intervals[i][0] < newInterval[0] {
			newInterval[0] = intervals[i][0]
		}
		if intervals[i][1] > newInterval[1] {
			newInterval[1] = intervals[i][1]
		}
		i++
	}
	result = append(result, newInterval)
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}

	return result
}
func main() {
	fmt.Println(merge([][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}))

	fmt.Println(insert(
		[][]int{{1, 3}, {6, 9}},
		[]int{2, 5},
	))
}