56. 合并区间(Merge Intervals)M

英文题目

• Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

• Example 1:

• Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
  Output: [[1,6],[8,10],[15,18]]
  Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
  

• Example 2:

• Input: intervals = [[1,4],[4,5]]
  Output: [[1,5]]
  Explanation: Intervals [1,4] and [4,5] are considered overlapping.
  

• Constraints:

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= start_i <= end_i <= 10^4

中文题目

• 以数组 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] 可被视为重叠区间。
  

• 提示：

• 1 <= intervals.length <= 10^4

• intervals[i].length == 2

• 0 <= start_i <= end_i <= 10^4

排序

• 时间复杂度O(nlogn)，其中n是区间的数量，除去排序的开销，只需要一次线性扫描，所以主要的时间开销是排序的 O(n logn)

• 空间复杂度O(log n)

  # python3: 时间 40 ms, 击败 98.6%; 内存 19.2 MB, 击败 59.3%
  class Solution:
      def merge(self, intervals: List[List[int]]) -> List[List[int]]:
          # 先将列表中的区间按照左端点升序排序
          intervals.sort(key=lambda x:x[0])
          merged  = []
          for inter in intervals:
              # 如果列表尾空，或者当前区间与上一区间不重合，直接添加
              if not merged or merged[-1][1] < inter[0]:
                  # merged[-1][1]是列表最后一个元素的第二个元素
                  # inter[0] 是当前区间的第一个元素
                  merged.append(inter)
              else:
                  # 否则将当前区间和上一区间进行合并
                  merged[-1][1] = max(merged[-1][1], inter[1])
          return merged
  

  // c++: 时间 32 ms, 击败 79.32%; 内存 18.6 MB, 击败 44.2%
  class Solution {
  public:
      vector<vector<int>> merge(vector<vector<int>>& intervals) {
          sort(intervals.begin(), intervals.end());
          vector<vector<int>> merged;
          for (const vector<int> & inter : intervals) {
              if (merged.empty() || merged[merged.size()-1][1] < inter[0]) {
                  merged.push_back(inter);
              } else {
                  merged[merged.size()-1][1] = max(merged[merged.size()-1][1], inter[1]);
              }
          }
          return merged;
      }
  };
  

  // java: 时间 6 ms, 击败 98.18%; 内存 44.4 MB, 击败 70.10%
  class Solution {
      public int[][] merge(int[][] intervals) {
          Arrays.sort(intervals, new Comparator<int[]>(){
              public int compare(int[] interval1, int[] interval2) {
                  return interval1[0] - interval2[0];
              }
          });
          List<int[]> merged = new ArrayList<int[]>();
          for (int[] inter : intervals) {
              if (merged.size() == 0 || merged.get(merged.size()-1)[1] < inter[0]) {
                  merged.add(inter);
              } else {
                  merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], inter[1]);
              }
          }
          return merged.toArray(new int[merged.size()][]);
      }
  }
  

  // go: 时间 20 ms, 击败 65.31%; 内存 6.6 MB, 击败 41.70%
  func merge(intervals [][]int) [][]int {
      sort.Slice(intervals, func(i, j int) bool {
          return intervals[i][0] < intervals[j][0]
      })
      merged := [][]int{}
      for _, inter := range intervals {
          if len(merged) == 0 || merged[len(merged)-1][1] < inter[0] {
              merged = append(merged, inter)
          } else {
              merged[len(merged)-1][1] = MaxInt(merged[len(merged)-1][1], inter[1])
          }
      }
      return merged
  }
  
  func MaxInt(i, j int) int {
      if i > j {
          return i
      }
      return j
  }
  

  // javascript: 时间 88 ms, 击败 88.56%; 内存 47.3 MB, 击败 71.32%
  /**
   * @param {number[][]} intervals
   * @return {number[][]}
   */
  var merge = function(intervals) {
      intervals.sort((a, b) => a[0] - b[0]);
      const merged = new Array();
      for (const inter of intervals) {
          if (!merged.length || merged[merged.length-1][1] < inter[0]) {
              merged.push(inter);
          } else {
              merged[merged.length-1][1] = Math.max(merged[merged.length-1][1], inter[1]);
          }
      }
      return merged;
  };