Question

How to add a new interval into a sorted array of non‑overlapping intervals in Go

Answer 1

package main

import (
    "fmt"
)

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

    // 1. Add all intervals that end BEFORE the new interval starts.
    // These cannot overlap.
    for i < n && intervals[i][1] < newInterval[0] {
        result = append(result, intervals[i])
        i++
    }

    // 2. Merge all intervals that DO overlap with the new interval.
    // Overlap condition: intervals[i].start <= newInterval.end
    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++
    }

    // Add the merged interval
    result = append(result, newInterval)

    // 3. Add all remaining intervals (those starting AFTER new interval ends)
    for i < n {
        result = append(result, intervals[i])
        i++
    }

    return result
}

func main() {
    intervals := [][]int{
        {1, 3},
        {6, 8},
        {13, 18},
    }

    newInterval1 := []int{9, 11}
    updated := insertInterval(intervals, newInterval1)

    newInterval2 := []int{2, 5}
    updated = insertInterval(updated, newInterval2)

    fmt.Println("Updated intervals:")
    for _, iv := range updated {
        fmt.Printf("[%d,%d] ", iv[0], iv[1])
    }
}


/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18] 

*/

 

70+ SQL courses for beginners and professionals