合并区间的题目描述
给定一个区间集合，目标是把所有重叠的区间合并成尽可能少的区间。
示例 1:
输入: inteRvals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 与 [2,6] 重叠，将它们合并为 [1,6]。
示例 2:
输入: inteRvals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 与 [4,5] 视为重叠区间。
提示：
inteRvals[i][0] <= inteRvals[i][1]
本题的关键在于排序。应该按左边界排序还是按右边界排序呢？
答案都可以！
通常选择按左边界从小到大排序。排序后，局部贪心的思路是：若当前区间的左边界不大于前一个区间的右边界，则两者有重叠，应进行合并；否则，当前区间不与之前的区间重叠，可以直接加入结果集。
通过这种局部贪心，可以得到全局最优：合并所有重叠的区间。
为什么这样成立？若 inteRvals[i][0] <= inteRvals[i - 1][1]，那么 inteRvals[i] 的左边界位于前一组区间的覆盖范围内，因此两者必有重叠。
合并区间的核心在于，若需要合并，则用左边界取两者中的较小值，用右边界取两者中的较大值，形成一个新的区间，放入结果集；若不需要合并，就直接把当前区间放入结果集。
实现要点
以左边界从小到大排序后，遍历区间，维护一个“当前合并区间”的起止。若下一个区间的左边界在当前区间的右边界之内，则扩大右边界；否则，将当前合并区间加入结果，并开启一个新的合并区间。
时间复杂度：O(n log n)，排序的代价决定了整体时间。空间复杂度：O(1)（若不计入返回结果的存储）或 O(m) 其中 m 是结果区间数量。
在贪心思路的学习中，直觉很重要。若能凭常识直接得出解法，就不易意识到其实是在使用贪心。然而，一旦第一直觉一时想不出，往往就需要更多练习与对题目的反复打磨。
要深入理解贪心，可以参考系统的练习与讲解，逐步积累经验。
如果你在学习路径上有疑问，建议多做题、反复归纳规律，逐步形成直觉。
相关语言版本
Java
Python
Go
JavaScript
