56. Merge Intervals

题目

Given a collection of intervals, merge all overlapping intervals.

题意

给定间隔的集合，合并所有重叠的间隔。

例子

Input: [[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].

题解

直接的想法，两层循环，固定当前元素，然后和后面的元素结合判断是否能够合并，能够合并的将其合并然后再重新遍历。在原数组上进行合并操作

代码

func merge(intervals [][]int) [][]int {
    N := len(intervals)
    if N==0{
        return nil
    }
    
    if len(intervals[0])!=2{
        return nil
    }
    
    i := 0
    j := 1
    for i<len(intervals){
        j=i+1
        for j<len(intervals){
            switch NeedMerge(intervals[i],intervals[j]){
            case 0:
                continue
            case 1:
                intervals[i][1]=intervals[j][1]
                intervals=append(intervals[:j],intervals[j+1:]...)
                j=i+1
            case 2:
                intervals=append(intervals[:j],intervals[j+1:]...)
                j=i+1
            case 3:
                intervals[i][0]=intervals[j][0]
                intervals=append(intervals[:j],intervals[j+1:]...)
                j=i+1
            case 4:
                intervals[i][0]=intervals[j][0]
                intervals[i][1]=intervals[j][1]
                intervals=append(intervals[:j],intervals[j+1:]...)
                j=i+1
            case -1:
                j++
            }
        } 
        i++
    }
    return intervals
} 

func NeedMerge(inter1,inter2 []int)int{
    if inter2[0]>=inter1[0]&&inter2[0]<=inter1[1]{
        if inter2[1]>=inter1[1]{
            return 1
        }else{
            return 2
        }
    }
    
    if inter1[0]>=inter2[0]&&inter1[0]<=inter2[1]{
        if inter1[1]>=inter2[1]{
            return 3
        }else{
            return 4
        }
    }
    return -1
}

总结

没有去找更优的解法，简单粗暴的解法，时间效率很低，但是空间效率很高233。