给出一个区间的集合，请合并所有重叠的区间。
示例 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, 快乐和性能总会有个平衡
