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.
