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

题目:

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 57. Insert Interval 插入区间 (C++/Java)


下一篇:IoT高级设备检索