56.合并区间

链接：56.合并区间
难度：Medium
标签：数组、排序
简介：给出一个区间的集合，请合并所有重叠的区间。

题解 1 - javascript

• 编辑时间：2020-04-16
• 执行用时：104ms
• 内存消耗：37.2MB
• 编程语言：javascript
• 解法介绍：先排序，再一次判断是否包含。

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  let res = [];
  intervals = intervals.sort((arr1, arr2) => arr1[0] - arr2[0]);
  const include = (num, left, right) => num >= left && num <= right;
  for (let i = 0, len = intervals.length; i < len; i++) {
    if (i === 0) {
      res.push(intervals[i]);
      continue;
    }
    const arr = intervals[i];
    const [left, right] = arr;
    const oldArr = res.pop();
    const [oldLeft, oldRight] = oldArr;
    if (include(left, oldLeft, oldRight)) {
      if (include(right, oldLeft, oldRight)) res.push(oldArr);
      else res.push([oldLeft, right]);
    } else {
      res.push(oldArr, arr);
    }
  }
  return res;
};

题解 2 - cpp

• 编辑时间：2021-12-23
• 执行用时：16ms
• 内存消耗：13.7MB
• 编程语言：cpp
• 解法介绍：排序后合并。

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.size() > 0 && ans[ans.size() - 1][1] >= interval[0]) {
                ans[ans.size() - 1][1] =
                    max(interval[1], ans[ans.size() - 1][1]);
            } else {
                ans.push_back(interval);
            }
        }
        return ans;
    }
};

题解 3 - python

• 编辑时间：2023-08-27
• 执行用时：56ms
• 内存消耗：19.6MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda o: o[0])
        res = []
        for [start, end] in intervals:
            if not len(res) or res[-1][1] < start:
                res.append([start, end])
            else:
                res[-1][1] = max(res[-1][1], end)
        return res

题解 4 - rust

• 编辑时间：2023-08-27
• 执行用时：8ms
• 内存消耗：2.83MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        intervals.sort_by_key(|o| o[0]);
        let mut res: Vec<Vec<i32>> = vec![];
        for item in intervals {
            if res.is_empty() || res.last().unwrap()[1] < item[0] {
                res.push(item);
            } else {
                res.last_mut().unwrap()[1] = res.last_mut().unwrap()[1].max(item[1]);
            }
        }
        res
    }
}