LeetCode 56. Merge Intervals 合并区间 (C++/Java)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode 56. Merge Intervals 合并区间 (C++/Java)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1957字，纯文字阅读大概需要3分钟。

内容图文

题目：

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.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

分析：

给定一个区间的集合，合并所有重复的区间。

也就是将重复的区间合并成一个大的区间，例如[1,5]和[3,7]将会合并成[1,7]，做法就是先将区间按左端点值由小到大排序，然后遍历区间，当后一个区间的左端点值大于它前一个区间的右端点值，代表两个区间无重复部分，将前一个加入到结果中，反之，代表有重复的，需要合并两个区间，由于区间的顺序由左端点值排序，则合并后的区间的左端点值等于前一个区间的左端点值，而右端点值则在两个区间的右端点值中取最大值，因为有可能发生包含这种情况，比如[1,7]和[3,5]这种，合并后就还是[1,7]。

程序：

C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if(intervals.size() == 0)
            return {};
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end(), cmp());
        for(auto interval:intervals){
            if(res.empty())
                res.push_back(interval);
            else if(res.back()[1] < interval[0])
                res.push_back(interval);
            else{
                auto t = res.back();
                res.pop_back();
                res.push_back({t[0], max(t[1], interval[1])});
            }
        }
        return res;
    }
    struct cmp {
        bool operator() (const vector<int>& A, const vector<int>& B) {
            return A[0] < B[0];
        }
    };
};

Java

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length == 0)
            return intervals;
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[0] - o2[0];
        });
        LinkedList<int[]> res = new LinkedList<>();
        for(int[] interval:intervals){
            if(res.isEmpty())
                res.add(interval);
            else if(res.getLast()[1] < interval[0])
                res.add(interval);
            else{
                int[] t = res.removeLast();
                res.add(new int[]{t[0], Math.max(t[1], interval[1])});
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

内容总结

以上是互联网集市为您收集整理的LeetCode 56. Merge Intervals 合并区间 (C++/Java)全部内容，希望文章能够帮你解决LeetCode 56. Merge Intervals 合并区间 (C++/Java)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端