题解 | #合并区间#

package main

//先做排序然后再一个个区间进行合并
import . "nc_tools"
import "sort"

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param intervals Interval类一维数组
 * @return Interval类一维数组
 */


type SortInterval []*Interval

func (s SortInterval) Len() int {
	return len(s)
}

func (s SortInterval) Less(i, j int) bool {
	if s[i].Start < s[j].Start {
		return true
	}
	if s[i].Start == s[j].Start {
		return s[i].End < s[j].End
	}
	return false
}

func (s SortInterval) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func merge(intervals []*Interval) []*Interval {
	// write code here
    if len(intervals) == 0 {
		return intervals
	}
	//排序好
	sort.Sort(SortInterval(intervals))

	//合并区间
	res := make([]*Interval, 0)
	curIv := intervals[0]
	for i := 1; i < len(intervals); i++ {
		tmpIv := intervals[i]
		if tmpIv.Start > curIv.End {
			res = append(res, curIv)
			curIv = tmpIv
			continue
		}
		//可能存在交叉；进行合并
		tmpStart := curIv.Start
		if tmpIv.Start < tmpStart {
			tmpStart = tmpIv.Start
		}
		tmpEnd := curIv.End
		if tmpIv.End > tmpEnd {
			tmpEnd = tmpIv.End
		}
		curIv.Start = tmpStart
		curIv.End = tmpEnd
	}
    	res = append(res,curIv)
	return res
}