Merge Intervals - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Merge Intervals" Problem in Go

Difficulty: Medium | Tags: Array, Sorting

Introduction

The "Merge Intervals" problem requires merging overlapping intervals in a given list to produce a list of non-overlapping intervals. This is a common problem in scheduling and time management applications.

Problem Analysis

Given a list of intervals, where each interval is represented as [start, end], we need to merge any overlapping intervals. For example, [[1,3],[2,6]] should be merged into [[1,6]] because the intervals overlap. Non-overlapping intervals like [[8,10],[15,18]] remain unchanged.

Solution Approach

The solution involves sorting the intervals by their start values. After sorting, we iterate through the intervals, merging them if they overlap with the last merged interval. If they don't overlap, we add the current interval to the result list.

Go Implementation


package main
import (
"fmt"
"sort"
)
func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return intervals
    }
    // Sort intervals based on the start value
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    merged := [][]int{intervals[0]}
    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        current := intervals[i]
        if current[0] <= last[1] {
            // Merge the intervals
            if current[1] > last[1] {
                last[1] = current[1]
            }
        } else {
            merged = append(merged, current)
        }
    }
    return merged
}
func main() {
    intervals1 := [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
    fmt.Println(merge(intervals1)) // Output: [[1 6] [8 10] [15 18]]
    intervals2 := [][]int{{1, 4}, {4, 5}}
    fmt.Println(merge(intervals2)) // Output: [[1 5]]
}

Complexity Analysis

The time complexity is O(n log n) due to the sorting step, where n is the number of intervals. The space complexity is O(n) to store the merged intervals, which in the worst case could be the same as the input size.

Testing and Examples

Test cases include:
1. [[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]
2. [[1,4],[4,5]] → [[1,5]]
3. [[1,4],[0,4]] → [[0,4]]
Edge cases include empty input or a single interval.

Best Practices and Tips

Always sort the intervals first to simplify the merging process. Handle edge cases like empty input early. Use clear variable names to improve readability. Test with overlapping intervals at the beginning, middle, and end of the list.

Read more