Solving the LeetCode "Insert Interval" Problem in Go

Difficulty: Medium | Tags: Array

Introduction

The "Insert Interval" problem requires inserting a new interval into a sorted list of non-overlapping intervals while maintaining the order and merging any overlapping intervals. This is a common problem in scheduling and time management applications.

Problem Analysis

Given a list of intervals sorted by their start times and a new interval, the task is to insert the new interval into the list such that the resulting list remains sorted and non-overlapping. If the new interval overlaps with any existing intervals, they should be merged into a single interval. For example, inserting [2,5] into [[1,3],[6,9]] results in [[1,5],[6,9]].

Solution Approach

The solution involves three steps: 1) Iterate through the intervals to find where the new interval should be inserted, 2) Merge any overlapping intervals, and 3) Construct the final list. The key is to handle the merging process correctly by comparing the start and end of the new interval with existing intervals.

Go Implementation

func insert(intervals [][]int, newInterval []int) [][]int {
    var result [][]int
    i := 0
    n := len(intervals)
    // Add all intervals before the newInterval
    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] {
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i++
    }
    result = append(result, newInterval)
    // Add remaining intervals
    for i < n {
        result = append(result, intervals[i])
        i++
    }
    return result
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Complexity Analysis

The algorithm runs in O(n) time, where n is the number of intervals, as it processes each interval exactly once. The space complexity is O(n) to store the result, which is optimal for this problem.

Testing and Examples

Test cases should include scenarios where the new interval does not overlap, overlaps partially, or completely overlaps with existing intervals. Edge cases include an empty intervals list or a new interval that extends beyond all existing intervals.

Best Practices and Tips

Ensure the merging logic correctly updates the new interval's start and end. Use helper functions for min and max to improve readability. Always test edge cases, such as empty input or intervals at the boundaries.