关于算法:LeetCodeGolang-56-合并区间

以数组 intervals 示意若干个区间的汇合，其中单个区间为 intervals[i] = [starti, endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好笼罩输出中的所有区间。

示例：

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

1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104

排序后好解决，先贴代码（Go）：

type Intervals [][]int

func (k Intervals) Len() int {return len(k)
}

func (k Intervals) Less(i, j int) bool {return k[i][0] < k[j][0]
}

func (k Intervals) Swap(i, j int) {k[i][0], k[j][0] = k[j][0], k[i][0]
   k[i][1], k[j][1] = k[j][1], k[i][1]
}

func merge(intervals [][]int) [][]int {var result [][]int
   var k Intervals = intervals
   sort.Sort(k)
   left := k[0][0]
   right := k[0][1]
   for _, interval := range k {if interval[0] <= right {right = max(right, interval[1])
      } else {result = append(result, []int{left, right})
         left = interval[0]
         right = interval[1]
      }
   }
   result = append(result, []int{left, right})
   return result
}

func max(a int, b int) int {
   if a > b {return a}
   return b
}

首先咱们将 intervals 中的元素看作一个单元，则这个单元有两个次要属性，即左端点和右端点。

咱们了解题意，有点像合并重叠单元从而寻找 连通重量 的数量的意思。咱们这里定义 连通重量 为不再与数组中任何其余单元重叠的一个单元。

如果两个单元 [a,b]，[c,d] 重叠，则须要满足断定式: a < c && b > c 或者 a > c && d > a，须要满足哪个条件取决于谁的左端点更靠左。

咱们能够通过对 intervals 排序，保障单元的左端点升序，即固定了断定式中的一个条件，即固定了 a < c 或者 a > c。之后只须要思考 b > c 和 d > a 即可。

排序后，咱们当初只须要在遍历 intervals 过程中，比拟第一个单元的右端点和第二个单元的左端点的值的大小，前者大于等于后者，可合并。合并后单元的右端点取两者的右端点的最大值。

继续合并过程，直到第一个单元的右端点小于第二个单元的左端点，则单元不可合并。则第一个单元就是所谓的 连通重量 了，记录一下。持续进行下一个 连通重量 的查找，直到遍历实现，咱们就失去了所有的 连通重量 了。

复杂度剖析：

工夫复杂度：O(nlogn)，其中 n 为区间的数量。除去排序的开销，咱们只须要一次线性扫描，所以次要的工夫开销是排序的 O(nlogn)。

空间复杂度：O(logn)，其中 n 为区间的数量。这里计算的是存储答案之外，应用的额定空间。O(logn) 即为排序所须要的空间复杂度

关于算法:LeetCodeGolang-56-合并区间

题目：

题解：