Merge Intervals(Golang)

Question

Solving the merge intervals problem in golang(link: https://leetcode.com/problems/merge-intervals/).

The Problem

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Code

package main

import (
    "fmt"
    "sort"
)

func main() {

    var intervals [][]int
    intervals = append(intervals, []int{7, 10})
    intervals = append(intervals, []int{3, 4})
    intervals = append(intervals, []int{2, 5})

    mergeIntervals(intervals)

}

func mergeIntervals(intervals [][]int) [][]int {

    if len(intervals) < 2{
        return intervals
    }
    var mergedIntervals [][]int
    fmt.Println("intervals :", intervals)
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    previousEndTime := intervals[0][1]
    for index, _ := range intervals {

        if index >= len(intervals)-1 {

            if index == len(intervals)-1 {
                mergedIntervals = append(mergedIntervals, []int{intervals[index][0], intervals[index][1]})
            }
            break
        }
        if index != 0 {
            //skip current interval if previous interval end time is higher
            if previousEndTime > intervals[index][1] {
                continue
            }
        }
        fmt.Println("comparing intervals ", intervals[index], "and ", intervals[index+1])
        if intervals[index][1] > intervals[index+1][1] {
            //check if current end time greater than end time of next interval
            mergedIntervals = append(mergedIntervals, []int{intervals[index][0], intervals[index][1]})
            previousEndTime = intervals[index][1]
        } else if intervals[index][1] >= intervals[index+1][0] {
            //the actual merge for overlapping  values
            mergedIntervals = append(mergedIntervals, []int{intervals[index][0], intervals[index+1][1]})
            previousEndTime = intervals[index+1][1]
        } else {
            //just include current interval with no overlap
            mergedIntervals = append(mergedIntervals, []int{intervals[index][0], intervals[index][1]})
            previousEndTime = intervals[index][1]
        }
    }

    fmt.Println("merged intervals ", mergedIntervals)
    return mergedIntervals
}

Looking for

• Code Bugs.
• Feel this code is too verbose.Any suggestions on how to optimize the code further.

Answer 1

Your code appears to fail on:

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Output:

intervals : [[1 3] [2 6] [8 10] [15 18]]
comparing intervals  [1 3] and  [2 6]
comparing intervals  [2 6] and  [8 10]
comparing intervals  [8 10] and  [15 18]
merged intervals  [[1 6] [2 6] [8 10] [15 18]]

---

Try to simplify your code to make it more readable. For example,

package main

import (
    "fmt"
    "sort"
)

func merge(intervals [][]int) [][]int {
    const start, end = 0, 1

    var merged [][]int

    if len(intervals) > 1 {
        sort.Slice(intervals, func(i, j int) bool {
            return intervals[i][start] < intervals[j][start]
        })
    }

    for _, interval := range intervals {
        last := len(merged) - 1
        if last < 0 || interval[start] > merged[last][end] {
            merged = append(merged,
                []int{start: interval[start], end: interval[end]},
            )
        } else if interval[end] > merged[last][end] {
            merged[last][end] = interval[end]
        }
    }

    return merged[:len(merged):len(merged)]
}

func main() {
    tests := []struct {
        intervals [][]int
    }{
        {[][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}},
        {[][]int{{1, 4}, {4, 5}}},
        {[][]int{{1, 2}}},
        {[][]int{}},
        {[][]int{{7, 10}, {3, 4}, {2, 5}}},
    }

    for _, tt := range tests {
        fmt.Print(tt.intervals)
        fmt.Println(" ->", merge(tt.intervals))
    }
}

Playground: https://play.golang.org/p/Akgsws42JfX

Output:

[[1 3] [2 6] [8 10] [15 18]] -> [[1 6] [8 10] [15 18]]
[[1 4] [4 5]] -> [[1 5]]
[[1 2]] -> [[1 2]]
[] -> []
[[7 10] [3 4] [2 5]] -> [[2 5] [7 10]]