← Back to DevBytes
Go August 05, 2026 11 min read

Solving Insert Interval in Go: Step-by-Step Guide

Introduction to Insert Interval

The Insert Interval problem is a classic algorithmic challenge frequently encountered in coding interviews and real-world scheduling applications. Given a list of non-overlapping intervals sorted by their start times, and a new interval to insert, the task is to insert the new interval into the list while merging any overlapping intervals. The result should remain a list of non-overlapping intervals sorted by start time.

In this tutorial, we will walk through solving this problem using Go (Golang), covering the underlying logic, a step-by-step implementation, testing strategies, and best practices to write clean and efficient code.

Understanding the Problem

Before diving into the solution, let us clearly define the problem. You are given:

Your goal is to insert the new interval into the existing list, merging any intervals that overlap with the new one, and return the resulting list of intervals.

Example

Consider the following example:

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

Here, the new interval [2,5] overlaps with [1,3] because 2 is less than or equal to 3. After merging, we get [1,5]. The interval [6,9] does not overlap, so it remains unchanged.

Why It Matters

The Insert Interval problem is more than just an interview exercise. It has practical applications in various domains:

Mastering this problem helps you develop a strong intuition for working with sorted data, handling edge cases, and writing efficient linear-time algorithms.

Approach to the Solution

The key insight is that since the input intervals are already sorted, we can process them in a single pass. We divide the intervals into three logical groups relative to the new interval:

  1. Intervals that come before the new interval: These end before the new interval starts. Add them directly to the result.
  2. Intervals that overlap with the new interval: These start before or at the same time as the new interval ends, and end after or at the same time as the new interval starts. Merge them into the new interval.
  3. Intervals that come after the new interval: These start after the new interval ends. Add them directly to the result.

By processing the intervals in order, we can handle all three cases in a single loop, achieving O(n) time complexity where n is the number of intervals.

Step-by-Step Breakdown

Let us break down the algorithm into clear steps:

Implementing the Solution in Go

Now let us translate this approach into Go code. We will define an Interval type and implement the insert function.

package main

import (
	"fmt"
)

// Interval represents a time range with a start and end.
type Interval struct {
	Start int
	End   int
}

// Insert inserts a new interval into a sorted, non-overlapping list of intervals,
// merging any overlapping intervals.
func Insert(intervals []Interval, newInterval Interval) []Interval {
	result := []Interval{}
	i := 0
	n := len(intervals)

	// Step 1: Add all intervals that come before the new interval.
	for i < n && intervals[i].End < newInterval.Start {
		result = append(result, intervals[i])
		i++
	}

	// Step 2: Merge all overlapping intervals with the new interval.
	for i < n && intervals[i].Start <= newInterval.End {
		if intervals[i].Start < newInterval.Start {
			newInterval.Start = intervals[i].Start
		}
		if intervals[i].End > newInterval.End {
			newInterval.End = intervals[i].End
		}
		i++
	}

	// Step 3: Add the merged new interval.
	result = append(result, newInterval)

	// Step 4: Add all remaining intervals that come after the new interval.
	for i < n {
		result = append(result, intervals[i])
		i++
	}

	return result
}

func main() {
	intervals := []Interval{
		{Start: 1, End: 3},
		{Start: 6, End: 9},
	}
	newInterval := Interval{Start: 2, End: 5}

	result := Insert(intervals, newInterval)

	fmt.Println("Result:")
	for _, interval := range result {
		fmt.Printf("[%d, %d] ", interval.Start, interval.End)
	}
	fmt.Println()
}

When you run this program, the output will be:

Result:
[1, 5] [6, 9]

How the Code Works

Let us trace through the code with the example input [[1,3], [6,9]] and [2,5]:

The final result is [[1,5], [6,9]], which is correct.

Handling Edge Cases

A robust solution must handle several edge cases. Let us examine them:

Empty Input List

If the input list is empty, the result should simply contain the new interval.

intervals := []Interval{}
newInterval := Interval{Start: 5, End: 7}
// Result: [[5, 7]]

New Interval at the Beginning

If the new interval starts before all existing intervals and does not overlap, it should be inserted at the front.

intervals := []Interval{{Start: 5, End: 7}, {Start: 10, End: 12}}
newInterval := Interval{Start: 1, End: 3}
// Result: [[1, 3], [5, 7], [10, 12]]

New Interval at the End

If the new interval starts after all existing intervals, it should be appended at the end.

intervals := []Interval{{Start: 1, End: 3}, {Start: 5, End: 7}}
newInterval := Interval{Start: 10, End: 12}
// Result: [[1, 3], [5, 7], [10, 12]]

New Interval Overlapping Multiple Intervals

The new interval may overlap with several existing intervals, all of which need to be merged.

intervals := []Interval{
	{Start: 1, End: 2},
	{Start: 3, End: 5},
	{Start: 6, End: 7},
	{Start: 8, End: 10},
	{Start: 12, End: 16},
}
newInterval := Interval{Start: 4, End: 9}
// Result: [[1, 2], [3, 10], [12, 16]]

New Interval Encompassing All Intervals

If the new interval covers all existing intervals, the result should be just the new interval.

intervals := []Interval{{Start: 2, End: 3}, {Start: 5, End: 7}}
newInterval := Interval{Start: 1, End: 10}
// Result: [[1, 10]]

Writing Tests for the Solution

Testing is crucial to ensure your solution handles all scenarios correctly. Go's built-in testing framework makes this straightforward. Here is a comprehensive test file:

package main

import (
	"reflect"
	"testing"
)

func TestInsert(t *testing.T) {
	tests := []struct {
		name        string
		intervals   []Interval
		newInterval Interval
		expected    []Interval
	}{
		{
			name:        "overlap with first interval",
			intervals:   []Interval{{Start: 1, End: 3}, {Start: 6, End: 9}},
			newInterval: Interval{Start: 2, End: 5},
			expected:    []Interval{{Start: 1, End: 5}, {Start: 6, End: 9}},
		},
		{
			name:        "empty input list",
			intervals:   []Interval{},
			newInterval: Interval{Start: 5, End: 7},
			expected:    []Interval{{Start: 5, End: 7}},
		},
		{
			name:        "new interval at beginning",
			intervals:   []Interval{{Start: 5, End: 7}, {Start: 10, End: 12}},
			newInterval: Interval{Start: 1, End: 3},
			expected:    []Interval{{Start: 1, End: 3}, {Start: 5, End: 7}, {Start: 10, End: 12}},
		},
		{
			name:        "new interval at end",
			intervals:   []Interval{{Start: 1, End: 3}, {Start: 5, End: 7}},
			newInterval: Interval{Start: 10, End: 12},
			expected:    []Interval{{Start: 1, End: 3}, {Start: 5, End: 7}, {Start: 10, End: 12}},
		},
		{
			name: "new interval overlapping multiple",
			intervals: []Interval{
				{Start: 1, End: 2},
				{Start: 3, End: 5},
				{Start: 6, End: 7},
				{Start: 8, End: 10},
				{Start: 12, End: 16},
			},
			newInterval: Interval{Start: 4, End: 9},
			expected: []Interval{
				{Start: 1, End: 2},
				{Start: 3, End: 10},
				{Start: 12, End: 16},
			},
		},
		{
			name:        "new interval encompasses all",
			intervals:   []Interval{{Start: 2, End: 3}, {Start: 5, End: 7}},
			newInterval: Interval{Start: 1, End: 10},
			expected:    []Interval{{Start: 1, End: 10}},
		},
		{
			name:        "adjacent intervals should merge",
			intervals:   []Interval{{Start: 1, End: 5}},
			newInterval: Interval{Start: 5, End: 7},
			expected:    []Interval{{Start: 1, End: 7}},
		},
	}

	for _, tt := range tests {
		t.Run(tt.name, func(t *testing.T) {
			result := Insert(tt.intervals, tt.newInterval)
			if !reflect.DeepEqual(result, tt.expected) {
				t.Errorf("got %v, want %v", result, tt.expected)
			}
		})
	}
}

Run the tests with the following command:

go test -v

Complexity Analysis

Understanding the time and space complexity of your solution is essential:

This is optimal because we must examine every interval at least once to determine whether it overlaps with the new interval.

Best Practices

Here are some best practices to keep in mind when implementing this solution and similar interval-based problems:

Use Clear and Descriptive Variable Names

Avoid single-letter variable names in production code. Use names like currentInterval or mergedInterval to improve readability.

Leverage Go's Slice Operations Carefully

Go slices are powerful but can lead to subtle bugs if not handled correctly. Always pre-allocate the result slice when you know the approximate size to avoid unnecessary reallocations:

result := make([]Interval, 0, len(intervals)+1)

Handle Edge Cases Explicitly

Even though our algorithm naturally handles edge cases like empty input, it is good practice to add explicit checks for clarity and to make the intent obvious to other developers:

func Insert(intervals []Interval, newInterval Interval) []Interval {
	if len(intervals) == 0 {
		return []Interval{newInterval}
	}
	// ... rest of the implementation
}

Consider Using a Two-Dimensional Slice Alternative

If you prefer working with raw slices instead of a struct, you can represent intervals as [][]int. This is common in competitive programming and LeetCode-style problems:

func insert(intervals [][]int, newInterval []int) [][]int {
	result := [][]int{}
	i := 0
	n := len(intervals)

	// Add intervals before the new interval
	for i < n && intervals[i][1] < newInterval[0] {
		result = append(result, intervals[i])
		i++
	}

	// Merge overlapping intervals
	for i < n && 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)

	// Add remaining intervals
	for i < n {
		result = append(result, intervals[i])
		i++
	}

	return result
}

Write Comprehensive Tests

Always test your solution against a variety of inputs, including edge cases. Table-driven tests in Go are an excellent way to organize and run multiple test scenarios cleanly.

Document Your Code

Add comments explaining the logic, especially for non-trivial conditions. This helps future maintainers (including yourself) understand the reasoning behind the implementation:

// Merge overlapping intervals by taking the minimum start
// and maximum end of the overlapping intervals.
for i < n && intervals[i].Start <= newInterval.End {
    if intervals[i].Start < newInterval.Start {
        newInterval.Start = intervals[i].Start
    }
    if intervals[i].End > newInterval.End {
        newInterval.End = intervals[i].End
    }
    i++
}

Common Mistakes to Avoid

When solving the Insert Interval problem, developers often make the following mistakes:

Extending the Solution

Once you have mastered the basic Insert Interval problem, consider these related challenges to deepen your understanding:

Each of these problems builds on the same core concepts of interval comparison, sorting, and merging.

Conclusion

The Insert Interval problem is a fundamental algorithmic challenge that tests your ability to work with sorted data, handle edge cases, and write efficient linear-time solutions. By breaking the problem into three logical phases—intervals before the new interval, overlapping intervals, and intervals after—you can implement a clean and correct solution in Go. Remember to handle edge cases explicitly, write comprehensive tests, and follow best practices such as pre-allocating slices and using descriptive variable names. With the approach outlined in this tutorial, you are well-equipped to tackle not only the Insert Interval problem but also a wide range of related interval-based challenges that you may encounter in both interviews and real-world applications.

— Ad —

Google AdSense will appear here after approval

← Back to all articles