Insert Interval into Sorted List in DSA Go - Build from Scratch

Insert Interval into Sorted List

📖 Scenario: You are managing a schedule of booked time slots represented as intervals. Each interval is a pair of start and end times. The schedule is sorted by start times and intervals do not overlap.Now, you want to add a new time slot to this schedule. You need to insert this new interval into the list and merge any overlapping intervals to keep the schedule clean and sorted.

🎯 Goal: Build a Go program that inserts a new interval into a sorted list of non-overlapping intervals and merges any overlaps.

📋 What You'll Learn

Create a slice of intervals called intervals with the exact values: {{1, 3}, {6, 9}}

Create a new interval called newInterval with the exact values: {2, 5}

Write a function insertInterval that takes intervals and newInterval and returns the merged intervals slice

Print the merged intervals in the format: [[1 5] [6 9]]

💡 Why This Matters

🌍 Real World

Managing meeting schedules, booking systems, or calendar events where time slots must be merged to avoid conflicts.

💼 Career

Understanding interval merging is useful for software roles involving scheduling, calendar apps, resource allocation, and time management features.

1

Create the initial intervals slice

Create a slice of intervals called intervals with the exact values: {{1, 3}, {6, 9}}

DSA Go

// Your code here

Hint

Define a slice named intervals with two Interval structs: {1, 3} and {6, 9}.

2

Create the new interval to insert

Create a new interval called newInterval with the exact values: {2, 5}

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func main() {
    intervals := []Interval{{1, 3}, {6, 9}}
    // Your code here

Hint

Define a variable named newInterval as an Interval struct with start 2 and end 5.

3

Write the insertInterval function

Write a function called insertInterval that takes intervals and newInterval as parameters and returns a slice of merged intervals after inserting newInterval. Use the variables intervals and newInterval exactly as given.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

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

    // Write insertInterval function call and assign result to merged
    // Your code here
}

// Write insertInterval function below

Hint

Write a function insertInterval that merges the new interval into the sorted list by iterating and merging overlaps.

4

Print the merged intervals

Print the merged intervals slice called merged using fmt.Println(merged) to display the final schedule.

DSA Go

package main

import "fmt"

type Interval struct {
    start int
    end   int
}

func insertInterval(intervals []Interval, newInterval Interval) []Interval {
    var merged []Interval
    i := 0
    n := len(intervals)

    // Add all intervals ending before newInterval starts
    for i  newInterval.end {
            newInterval.end = intervals[i].end
        }
        i++
    }
    merged = append(merged, newInterval)

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

    return merged
}

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

    merged := insertInterval(intervals, newInterval)
    // Print the merged intervals below
    // Your code here
}

Hint

Use fmt.Println(merged) to print the final merged intervals.

Practice

1. What is the main goal when inserting a new interval into a sorted list of non-overlapping intervals?

easy

A. To merge overlapping intervals and keep the list sorted

B. To add the new interval at the end without merging

C. To remove all intervals that come before the new interval

D. To sort the list again after insertion

Solution

1. Step 1: Understand the problem context

   The list contains sorted, non-overlapping intervals. Inserting a new interval may cause overlaps.

2. Step 2: Determine the correct action

   We must merge any overlapping intervals with the new one to keep the list sorted and non-overlapping.

3. Final Answer:

   To merge overlapping intervals and keep the list sorted -> Option A

4. Quick Check:

   Insert interval = merge and keep sorted [OK]

Hint: Merge overlaps to keep intervals sorted and non-overlapping [OK]

Common Mistakes:

• Just appending without merging
• Removing intervals incorrectly
• Sorting again after insertion

2. Which Go syntax correctly declares a slice of intervals where each interval is a slice of two integers?

easy

A. intervals := [][2]int{{1, 3}, {6, 9}}

B. intervals := [][]int{1, 3, 6, 9}

C. intervals := []int{1, 3, 6, 9}

D. intervals := [][]int{{1, 3}, {6, 9}}

Solution

1. Step 1: Identify slice of slices syntax

   In Go, [][]int means a slice of slices of int, suitable for intervals like [start, end].

2. Step 2: Check each option

   intervals := [][]int{{1, 3}, {6, 9}} correctly uses [][]int with nested slices for intervals. intervals := [][2]int{{1, 3}, {6, 9}} uses array [2]int which is valid but less common. intervals := []int{1, 3, 6, 9} is a flat slice, not intervals. intervals := [][]int{1, 3, 6, 9} is invalid syntax.

3. Final Answer:

   intervals := [][]int{{1, 3}, {6, 9}} -> Option D

4. Quick Check:

   Slice of slices = [][]int{{start,end}} [OK]

Hint: Use [][]int for slice of intervals in Go [OK]

Common Mistakes:

• Using flat []int instead of [][]int
• Incorrect array vs slice syntax
• Missing curly braces for nested slices

3. What is the output of the following Go code snippet after inserting interval [2,5] into intervals [[1,2],[6,9]]?

intervals := [][]int{{1, 2}, {6, 9}}
newInterval := []int{2, 5}
// After insertion and merging
result := [][]int{{1, 5}, {6, 9}}
fmt.Println(result)

medium

A. [[1 2] [6 9] [2 5]]

B. [[1 2] [2 5] [6 9]]

C. [[1 5] [6 9]]

D. [[2 5] [6 9]]

Solution

1. Step 1: Insert and check overlap

   New interval [2,5] overlaps with [1,2] because 2 <= 2. Merge them to [1,5].

2. Step 2: Keep other intervals

   [6,9] does not overlap with [1,5], so it stays as is.

3. Final Answer:

   [[1 5] [6 9]] -> Option C

4. Quick Check:

   Merged intervals = [[1 5] [6 9]] [OK]

Hint: Merge overlapping intervals to combine ranges [OK]

Common Mistakes:

• Not merging overlapping intervals
• Appending new interval without sorting
• Incorrect interval order

4. Given this Go function snippet to insert an interval, what is the bug?

func insert(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    for _, interval := range intervals {
        if interval[1] < newInterval[0] {
            result = append(result, interval)
        } else if interval[0] > newInterval[1] {
            result = append(result, newInterval)
            newInterval = interval
        } else {
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
        }
    }
    result = append(result, newInterval)
    return result
}

medium

A. Appending newInterval multiple times causes duplicates

B. Not updating newInterval correctly during merge

C. Missing return statement

D. Incorrect comparison operators in if conditions

Solution

1. Step 1: Analyze appending logic

   When interval[0] > newInterval[1], newInterval is appended and then replaced by interval. This can cause multiple appends of newInterval.

2. Step 2: Identify duplicate insertion

   Because newInterval is appended inside the loop multiple times, duplicates appear in result.

3. Final Answer:

   Appending newInterval multiple times causes duplicates -> Option A

4. Quick Check:

   Multiple appends = duplicates [OK]

Hint: Append newInterval once after loop to avoid duplicates [OK]

Common Mistakes:

• Appending inside loop multiple times
• Not updating newInterval boundaries
• Forgetting to return result

5. You have intervals [[1,3],[6,9]] and want to insert [2,7]. What is the final list after insertion and merging?

hard

A. [[1,3],[2,7],[6,9]]

B. [[1,9]]

C. [[1,7],[6,9]]

D. [[1,9],[6,9]]

Solution

1. Step 1: Merge [2,7] with overlapping intervals

   [2,7] overlaps with [1,3] and [6,9]. Merge all three intervals into one covering from min start 1 to max end 9.

2. Step 2: Final merged interval

   The merged interval is [1,9], replacing the original two intervals.

3. Final Answer:

   [[1,9]] -> Option B

4. Quick Check:

   Merge all overlapping = [[1,9]] [OK]

Hint: Merge all overlapping intervals into one big interval [OK]

Common Mistakes:

• Partial merges leaving overlaps
• Appending without merging
• Incorrect interval boundaries