1
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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]]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.