56. 合并区间

56. 合并区间 - 力扣（LeetCode）

class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    std::sort(intervals.begin(), intervals.end(),
      [](const vector<int> &lhs, const vector<int> &rhs) {
        return lhs[0] < rhs[0] || (lhs[0] == rhs[0]) && lhs[1] < rhs[1];
      });

    int left = intervals[0][0];
    int right = intervals[0][1];
    vector<vector<int>> merged;
    for (int i = 1; i < intervals.size(); ++i) {
      if (intervals[i][0] <= right) {
        right = max(right, intervals[i][1]);
        continue;
      } else {
        merged.push_back({left, right});
        left = intervals[i][0];
        right = intervals[i][1];
      }
    }
    merged.push_back({left, right});
    return merged;
  }
};

不要忘记对数组中的数据采用先排序再操作的方法，尤其是当给出的数组有麻烦的乱序情况时。虽然这是在调用 std::sort()，但至少也是 \(\mathrm O(n \log n)\) 级别的。

二刷

class Solution {
  bool OrderedOverlap(const std::span<int> &Lhs, const std::span<int> &Rhs) {
    return Lhs[1] >= Rhs[0];
  }

public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.size() == 1)
      return intervals;
    // std::less<> automatically generates comparisons.
    std::sort(intervals.begin(), intervals.end());

    vector<vector<int>> Result{intervals.front()};
    for (int i = 0; i < intervals.size(); ++i) {
      // Try to use references as possible.
      vector<int> &Prev = Result.back();
      vector<int> &Curr = intervals[i];
      if (OrderedOverlap(Prev, Curr))
        Prev[1] = std::max(Prev[1], Curr[1]);
      else
        Result.push_back(Curr);
    }
    return Result;
  }
};

说实在的，这个题的解法不少，毕竟是纯模拟；但是像上面这样这么写应该还是最优雅的。我也是第一次知道 std::less<> 可以自动生成对于 vector<int> 的逐个比较运算符，压根不需要自己在 lambda 里手写。

其次就是，这道题还是可以多用用引用的。这里用引用的话语义还是非常明确的，也不用费心思去创建临时对象。

三刷

class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> Result;
    std::sort(intervals.begin(), intervals.end());

    int ThisStart = intervals.front()[0];
    int ThisEnd = intervals.front()[1];
    for (int i = 1; i < intervals.size(); ++i) {
      int Start = intervals[i][0];
      int End = intervals[i][1];
      if (Start <= ThisEnd) {
        ThisEnd = max(ThisEnd, End);
      } else {
        Result.push_back({ThisStart, ThisEnd});
        ThisStart = Start;
        ThisEnd = End;
      }
    }
    Result.push_back({ThisStart, ThisEnd});
    return Result;
  }
};

这样写有个不太美观的地方就是最后还得多写一行push_back。但是也还行吧，至少没有什么merged.back()[1]这种东西存在。