目录
合并区间
访问量:392

一、题目

给出一组区间,请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

案例1

输入:

[[10,30],[20,60],[80,100],[150,180]]

返回值:

[[10,60],[80,100],[150,180]]

案例2

输入:

[[0,10],[10,20]]

返回值:

[[0,20]]


二、实现

思路:1、排序区间;2.从前往后,逐一合并

/*
 * type Interval struct {
 *   Start int
 *   End int
 * }
 */

/**
 * 
 * @param intervals Interval类一维数组 
 * @return Interval类一维数组
*/
func merge( intervals []*Interval ) []*Interval {
    // write code here
    if len(intervals) <=1 {
        return intervals
    }
    
    // 排序
    sort.Slice(intervals, func(i,j int) bool{
        return intervals[i].Start < intervals[j].Start 
    })
    
    i:= 0
    for i < len(intervals) -1 {
        // 合并 i和i+1
        if intervals[i].End < intervals[i+1].Start {
            i++
            continue
        }
        
        if intervals[i].End  < intervals[i+1].End {
            intervals[i].End = intervals[i+1].End
        }
        
         // 去掉 intervals[i+1]这一项
        if i+1 == len(intervals) -1 {
            intervals = intervals[:i+1]
            break
        } else {
            intervals = append(intervals[:i+1], intervals[i+2:]...)
        }
    }
    
    return intervals
}

题目来源:牛客