合并区间

题目

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

具体思路

• 按区间左端点进行排序；
• 重新定义一个res，将每个待排的结果放入；
• 每次有冲突，修改res最右元素的右端点；
• 没有冲突直接放入res。

关键点：终止条件要加入最后一个元素，否则可以每处理一个区间，然后进行加入该区间，如果重复了，直接修改就可以，从而避免掉相关的收尾；

具体代码

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0])
            // 降序
            return a[0] < b[0];
        // 降序
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        vector<vector<int>> res;
        if (intervals.size() <= 1)
            return intervals;
        res.push_back(intervals[0]);
        int count = 0;
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] <= res[count][1])
                res[count][1] = max(intervals[i][1], res[count][1]);
            else {
                res.push_back(intervals[i]);
                count++;
            }
        }
        return res;
    }
};

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        if (intervals.size() <= 1)
            return intervals;
        sort(intervals.begin(), intervals.end(), cmp);
        res.push_back(intervals[0]);
        for (int i = 1; i < intervals.size(); i++) {
            if (res.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的
                res.back()[1] = max(res.back()[1], intervals[i][1]);
            } else {
                res.push_back(intervals[i]); // 区间不重叠
            }
            // if (intervals[i][0] <= intervals[i - 1][1]) {
            //     intervals[i][0] = min(intervals[i - 1][0], intervals[i][0]);
            //     intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
            // } else if (i == 1)
            //     res.push_back(intervals[0]);
            // res.push_back(intervals[i]);
        }
        return res;
    }
};

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (x, y) -> {
            return x[0] == y[0] ? x[1] - y[1] : x[0] - y[0];
        });

        int start = intervals[0][0];
        int end = intervals[0][1];
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= end) {
                start = Math.min(start, intervals[i][0]);
                end = Math.max(end, intervals[i][1]);
            } else {
                res.add(Arrays.asList(start, end));
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        res.add(Arrays.asList(start, end));
        return res.stream()
                .map(inner -> inner.stream()
                        .mapToInt(Integer::intValue)
                        .toArray())
                .toArray(int[][]::new);
    }
}

因为你已经对所有区间按起始位置 intervals[i][0] 进行了升序排序，所以在合并时，start 变量（当前合并区间的起始点）必然小于或等于 intervals[i][0]。因此，Math.min(start, intervals[i][0]) 的结果永远是 start，不需要再次计算。