合并区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

这题思路就是对左端点进行排序，然后看枚举数组的时候，看两个区间是否有重叠，如果有重叠，就把两个区间合并成一个区间。

class Solution {
public:
  static bool mycompare(vector<int>a,vector<int>b){
    return a[0] <b[0];
  }
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if(intervals.size()==0) return intervals;
    sort(intervals.begin(),intervals.end(),mycompare);
    vector<vector<int>> res;
    res.push_back(intervals[0]);
    for(int i=1;i<intervals.size();i++){
            
      if(res.back()[1] >=intervals[i][0]){//区间重叠了
        res.back()[1]=max(res.back()[1],intervals[i][1]);
      }else{
        res.push_back(intervals[i]);
      }
    }
    return res;
  }
};

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13