[Vssue]0056.合并区间.md

[youngyangyang04]

https://www.programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html

[Du1in9]

Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> result = new ArrayList<>();
result.add(intervals[0]);

for (int i = 1; i < intervals.length; i++) {
    int end = result.getLast()[1];
    if (intervals[i][0] <= end) {
        result.getLast()[1] = Math.max(end, intervals[i][1]);
    } else {
        result.add(intervals[i]);
    }
}
return result.toArray(new int[result.size()][]);

// 例: intervals = [[1,3],[2,6],[8,10],[15,18]], result = [[1,3]]
i = 1: end = 3, 满足 2 <= 3（有重叠）, b = 6, result = [[1,6]]
i = 2: end = 6, 不满足 8 <= 6（无重叠）, result = [[1,6],[8,10]]
i = 3: end = 10, 不满足 15 <= 10（无重叠）, result = [[1,6],[8,10],[15,18]]

[233zzl]

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