解析

排序法

这些区间按开头顺序排序后就变成了很容易合并的情况，难点在于对”std::sort应用于std::vector”的理解
sort(intervals.begin(), intervals.end());查看sort源码如下

可以看到两个参数情况下(第二个划线函数)使用less<>{}比较，而

less就是用<比较。

而在<vector>中已经重载了<,如下

第一个if内容我们不用管，是实现特殊存在按位存的vector<bool>比较的。
看else,这里就是调用lexicographical_compare,和字符串按字典序比较的思想一样，默认比较容器里第一个元素，第一个相等则顺位比较第二个

那么我们就可以用std::sort来轻松解决这道题了

//! nlogn,n -> 排序std::sort耗时nlogn；除返回值占地外，std::sort函数递归栈占地log(n)
class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>> &intervals) {
    if (intervals.empty()) {
      return vector<vector<int>>{};
    }

    vector<vector<int>> res;
    sort(intervals.begin(), intervals.end());
    res.emplace_back(intervals[0]);
    for (int i = 1; i < intervals.size(); ++i) {
      int left = intervals[i][0], right = intervals[i][1];
      if (res.back()[1] < left) {
        res.emplace_back(vector<int>{left, right});
      } else {
        res.back()[1] = max(res.back()[1], right);
      }
    }
    return res;
  }
};

2025-03-03 该篇文章被 HopoZ 打上标签: leetcode 归为分类: algo