跳转至

56 合并区间

以下两种做法思路是一样的,第一种是我自己写的,第二种是别人的题解

我觉得第二种更不容易写错,建议第二种

做法一

这种做法的思路是:

  1. 对区间左端点进行排序
  2. 通过取前一个区间的start和end,与当前区间的start和end进行比较,如果当前区间的start比前一个区间的end小,合并当前区间和前一个区间
  3. 如果当前区间的start比前一个区间的end大,将前一个区间放入答案

我们来思考最后两个区间

当遍历结束到最后一个区间,有两种情况:

  • 前一个区间的终点比当前区间的起点大,合并两个区间,end = max(end,intervals[i][1]); -> 此时合并后的区间没有放入答案
  • 前一个区间的终点比当前区间的起点小,将前一个区间放入答案,更新start = intervals[n - 1][0]和end = intervals[n - 1][1]; -> 此时最后一个区间没有放入答案

因此,我们需要多加一步,将最后的区间放入答案ans.push_back({start, end});

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        // 对区间左端点进行排序
        sort(intervals.begin(), intervals.end());
        // 前一个区间[start, end]的初始化
        int start = intervals[0][0];
        int end = intervals[0][1];
        vector<vector<int>> ans;
        for (int i = 1; i < n; i++) {
            // 如果前一个区间的终点比当前区间的起点大,说明要合并两个区间
            if (intervals[i][0] <= end)
                end = max(end,intervals[i][1]);
            // 否则,将前一个区间纳入答案,更新前一个区间[start, end]
            else {
                ans.push_back({start, end});
                start = intervals[i][0];
                end = intervals[i][1];
            }
        }
        // 以上处理了前n - 1个区间,还有最后一个区间没有放入答案
        ans.push_back({start, end});
        return ans;
    }
};

做法二

做法二聚焦于当前的区间,前一个区间放在ans的末端(把ans视作栈,ans.back()就是栈顶,通过更新ans.back()完成合并区间)

放入答案的方式是将当前区间放入ans(做法一是将前一个区间放入ans)

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        for(auto interval : intervals){
            if(!ans.empty() && ans.back()[1] >= interval[0])
                ans.back()[1] = max(ans.back()[1], interval[1]);
            else
                ans.push_back(interval);
        }
        return ans;
    }
};