1
2
3

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

1
2
3

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// 1. 将所有区间按首元素排序;
    /// 2. 依次判断排序后的元素是否重叠, 是否重叠根据每个区间的首元素是否<=最后区间的尾元素决定;
    /// 3. 将未重叠的区间直接加入到结果集中;
    /// 4. 重叠的区间,根据尾元素判断是否更新最后区间的尾范围;
    pub fn merge(intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        let mut res: Vec<Vec<i32>> = vec![];
        let mut intervals = intervals;

        //按首元素对所有区间进行排序
        intervals.sort_by(|a, b| a[0].cmp(&b[0])); 

        //遍历排序后的区间集合
        for val in intervals {
            // 根据当前区间和结果集最后一个区间的关系判断是否重叠
            match res.last_mut() {
                // 如果当前区间头和最后一个区间尾有重叠 
                Some(last_val) if val[0] <= last_val[1] =>  {
                    // 当当前重叠的区间尾部比最后一个区间尾长时
                    if val[1] > last_val[1] { 
                        last_val[1] = val[1]; //更新最后一个区间尾
                    }
                }
                //当前区间和之前区间没有重叠
                _ => res.push(val), //直接将当前区间加入到结果数组尾部
            }
        }

        res
    }
}
// @lc code=end

struct Solution;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

# @lc code=start
class Solution:
    '''
    - 先按第1个元素对区间进行排序；
    - 遍历已排序区间，如果有重叠(current[0]<=前一个item[1]), 则合并到前一个区间中；否则未重叠，将之前区间加到结果列表，重新设置待合并区间；
    '''
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals) < 1:
            return []
        sorted_intervals = sorted(intervals, key=lambda s: s[0])
        res = []
        pending = sorted_intervals[0]
        for current in sorted_intervals[1:]:
            if current[0] <= pending[1]:
                pending[1] = max(current[1], pending[1]) 
            else:
                res.append(pending)
                pending = current
        res.append(pending)
        return res

# @lc code=end