合并区间
Merge Intervals
题目详情
问题：合并区间
考察：数组、贪心
来源：Citadel
链接：https://www.jointaro.com/interviews/questions/merge-intervals/
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Example 1:
Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Example 2:
Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.
Constraints:
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
解析
思路：先按区间起点排序。依次扫描区间，若当前区间与结果最后一个重叠，就扩展结束点；否则开启新区间。
复杂度：排序 O(n log n)，扫描 O(n)，空间 O(n) 输出。