LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 先按照区间左边界值升序排序
• 对于两个区间，如果第一个区间的右边界与第二个区间的左边界不重合，则第一个区间是一个不重叠的区间，添加到结果中

[1, 3] [4, 5] => [1, 3] 是不重叠的区间，添加到结果中

• 如果两者重叠，合并两个区间的方法是，左边界取较小值，右边界取较大值，合并结果存储到右区间，继续与下一个区间比较

[1, 3] [2, 6] => [1, 6]
[1, 7] [2, 6] => [1, 7]

• 从左到右依次两两处理。最后一个区间不会执行上述操作，直接添加到结果中即可

class Solution {
 public:
  vector<vector<int>> merge(vector<vector<int>>& intervals) {
    vector<vector<int>> res;
    if (empty(intervals)) {
      return res;
    }
    sort(begin(intervals), end(intervals),
         [](auto& x, auto& y) { return x[0] < y[0]; });
    for (int i = 0; i < size(intervals) - 1; ++i) {
      if (intervals[i][1] < intervals[i + 1][0]) {
        res.emplace_back(intervals[i]);
      } else {
        intervals[i + 1][0] = intervals[i][0];
        intervals[i + 1][1] = max(intervals[i][1], intervals[i + 1][1]);
      }
    }
    res.emplace_back(intervals.back());
    return res;
  }
};