# Merge Intervals(Golang)

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.

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]]