LeetCode：56. Merge Intervals（合并区间）

怼烎@ 2022-04-05 13:44 205阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k][）][Leetcode_300. Longest Increasing Subsequence]**

--------------------

**文章目录：**

题目描述：

java实现方法1：

python实现方式1:

源码github地址：https://github.com/zhangyu345293721/leetcode

--------------------

### 题目描述： ###

给出一个区间的集合，请合并所有重叠的区间。

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）

--------------------

### java实现方法1： ###

/**
         * 合并区间
         *
         * @param intervals 区间数组
         * @return 合并后的区间
         */
        public int[][] merge(int[][] intervals) {
             if (intervals.length <= 1) {
                return intervals;
             }
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            List<int[]> list = new ArrayList<>();
            int[] curInterval = intervals[0];
            for (int i = 1; i < intervals.length; i++) {
                if (intervals[i][0] <= curInterval[1]) {
                    curInterval[1] = Math.max(intervals[i][1], curInterval[1]);
                } else {
                    list.add(curInterval);
                    curInterval = intervals[i];
                }
            }
            list.add(curInterval);
            int[][] ret = new int[list.size()][];
            for (int i = 0; i < list.size(); i++) {
                ret[i] = list.get(i);
            }
            return ret;
        }

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### python实现方式1: ###

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
            '''
                合并区间
            Args:
                intervals: 区间对象
            Returns:
                区间集合
            '''
            if not intervals or len(intervals) < 1:
                return intervals
            intervals.sort(key=lambda x: x[0])
            merged = []
            cur = intervals[0]
            for i in range(1, len(intervals)):
                if cur[1] >= intervals[i][0]:
                    cur[1] = max(cur[1], intervals[i][1])
                else:
                    merged.append(cur)
                    cur = intervals[i]
            merged.append(cur)
            return merged

时间复杂度：O(n)

空间复杂度：O(1)

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode