给出若干闭合区间，合并所有重叠的部分。

点此在线做题

样例 1:

输入: [(1,3)] 输出: [(1,3)] 

样例 2:

输入:  [(1,3),(2,6),(8,10),(15,18)] 输出: [(1,6),(8,10),(15,18)] 

解题思路

对应两个区间 a, b，如何判断它们相交？ 当 a, b 满足 max(a.start,b.start)<=min(a.end,b.end)max(a.start,b.start)<=min(a.end,b.end)时，两者相交。 我们应考虑某种排序方式，使得所有相交的区间对应一段连续的数组下标，这样方便我们进行之后的合并操作。 这种排序方式应该是对区间的左端点按从小到大的方式进行排序，假设我们存在一个已经按照上面方式排序的数组：[1，2][1，3][2，4][5，7][6，10][6，11]。 可以看出，当我遍历数组的时候，每次访问一个区间 ai，都能保证：如果 ai 和它前面的区间不相交，那么 ai 后面的任意区间都不能和 ai 前面的任意区间相交。这样就保证了时间复杂度为 O(n)级别，即不会出现其他的遍历。 比如区间[5，7]，他和前面的区间都没有相交，他后面的所有区间和它一样，没有和[5，7]前面的区间有交集。

代码思路

1. 对区间数组按区间的左端点 start 排序。
2. 将最后的区间赋值 lastinterval 为 intervals[0]。
3. 遍历输入，如果 lastinterval 和当前区间相交，合并两个区间。
4. 如果不相交，将 lastinterval 加入结果，并将 lastinterval 赋值为当前的区间。

复杂度分析

设区间的个数为 N 。 时间复杂度

• 排序的时间复杂度为 O(NlogN)。
• 遍历一遍数组的时间复杂度为 O(N)。
• 总时间复杂度为 O(NlogN)。 空间复杂度
• 空间复杂度为 O(n)，可能存在每一个区间都不与任何一段区间相交，返回的答案和传入的参数长度相等。

public class Solution {     /**      * @param intervals: interval list.      * @return: A new interval list.      */     public List<Interval> merge(List<Interval> intervals) {         if (intervals.size() == 0) {             return intervals;         }                  // 根据区间的 start 值排序         intervals.sort(Comparator.comparing(i -> i.start));                  List<Interval> result = new ArrayList<Interval>();         Interval lastInterval = intervals.get(0);                  // 如果两段区间有交集的话，合并两段区间         // 没有的话，将最后的区间加入答案，并令新的区间作为最后的区间         for (Interval interval: intervals) {             if (haveIntercation(lastInterval, interval)) {                 lastInterval = mergeTwoIntervals(lastInterval, interval);             }             else {                 result.add(lastInterval);                 lastInterval = interval;             }         }         result.add(lastInterval);                  return result;     }     // 合并两段区间     private Interval mergeTwoIntervals(Interval a, Interval b) {         return new Interval(Math.min(a.start, b.start), Math.max(a.end, b.end));     }     // 判断区间是否有交集，要满足较大的 start 小于等于较小的 end     private boolean haveIntercation(Interval a, Interval b) {         return Math.max(a.start, b.start) <= Math.min(a.end, b.end);     } }  

大佬有話說 (0)