题目:

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

示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

思路:

将数组进行预排序(O(logn)), 排序后的能够合并的数组一定是连在一起的, 在进行一次遍历就可以判断相邻的数组是否可以合并

ruby

# @param {Integer[][]} intervals
# @return {Integer[][]}
def merge(intervals)
    return intervals if intervals.empty?
	# 按数组第一位排序 
	arr = intervals.sort_by{|a| a[0]} 
	new_arr = [arr[0]]
	i, j = 0, 1
	# 遍历比较
	while j < arr.size
	    x = new_arr[i]
	    y = arr[j]
	    #重叠条件,即前一个区间的右区间大于等于后一个区间的左区间
	    if x[1] < y[0]
	        new_arr << y 
	        i += 1
	    else
	        x[1] = [x[1], y[1]].max
	    end
	    j += 1
	end
	new_arr
end

go

func merge(intervals [][]int) [][]int {
	if len(intervals) <= 1 {
		return intervals
	}
	//排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	new_intervals := [][]int{intervals[0]}
	i, j := 1, 0
    // 遍历
	for i < len(intervals) {
		if new_intervals[j][1] >= intervals[i][0] {
			if new_intervals[j][1] < intervals[i][1] {
				new_intervals[j][1] = intervals[i][1]
			}
		}else {
			new_intervals = append(new_intervals, intervals[i])
			j++
		}
		i++
	}
	return new_intervals
}

同样的逻辑 ruby 用了46ms, go用了12ms, 快乐和性能总会有个平衡