leetcode-56-合并区间 leetcode-56-合并区间

题目:
给出一个区间的集合，请合并所有重叠的区间。

示例 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] 可被视为重叠区间。

【leetcode-56-合并区间】思路:
将数组进行预排序(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

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, 快乐和性能总会有个平衡