LeetCode 56. Merge Intervals C++ 比较器与 Python 两种语言

最新推荐文章于 2022-04-23 13:39:21 发布

mooe1011

最新推荐文章于 2022-04-23 13:39:21 发布

阅读量207

点赞数

分类专栏： LeetCode C++ Python

本文链接：https://blog.csdn.net/mooe1011/article/details/90705251

版权

C++ 同时被 3 个专栏收录

26 篇文章

订阅专栏

Python

15 篇文章

订阅专栏

LeetCode

13 篇文章

订阅专栏

博客围绕合并重叠区间问题展开，给出示例，并提及先对输入排序，还给出了使用C++比较器格式以及Python相关内容，主要聚焦于信息技术领域的算法问题解决。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

# input:
[[1,3],[2,6],[8,10],[15,18]]
[[1,4],[4,5]]
[[1,4],[2,3]]
[[2,3],[4,5],[6,7],[8,9],[1,10]]
[[3,3],[0,1],[0,0]]

# output:
[[1,6],[8,10],[15,18]]
[[1,5]]
[[1,4]]
[[1,10]]
[[0,1],[3,3]]

先对输入排序，使用C++比较器格式：

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.empty())
            return {};
        vector<vector<int>>res;
        //keypoint
        sort(begin(intervals), end(intervals),
             [](vector<int> a, vector<int> b){return a[0]<b[0];});


        //法1
        int head=intervals[0][0],end=intervals[0][1];
        for(int i=1;i<intervals.size();i++){            
            if(end<intervals[i][0]){
                res.push_back({head,end});
                head=intervals[i][0];
            }
            if(end<intervals[i][1])
                end=intervals[i][1];
        }
        res.push_back({head,end});

        /*法二
        res.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            if(res.back()[1]<intervals[i][0]){
                res.push_back(intervals[i]);
            }
            else if(res.back()[1]<intervals[i][1]){
                res.back()[1]=intervals[i][1];
            }                
        }
        */

        return res;
    }

Python:

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if len(intervals)==0: return []
        intervals=sorted(intervals,key=lambda x : x[0])
        res=[intervals[0]]
        for n in intervals[1:]:
            if n[0] <= res[-1][1]:
                res[-1][1]=max(n[1],res[-1][1])
            else:
                res.append(n)
        return res