Leetcode56. 合并区间

文章目录

• 题目
• 原题链接
• 思路
• 代码

  题目

  以数组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 <= 104

  intervals[i].length == 2

  0 <= starti <= endi <= 104

  原题链接

  Leetcode56. 合并区间

  思路

  1. 将所有的区间排序

     

     我们发现有两种情况：

     

  2. 定义区间的左右端点，l = a[0][0], r = a[0][1] ,开始遍历

     情况一：

     没有交集（a[i][0] > r），则将第一个区间加入答案中，并更新左右端点(l = a[i][0], r = a[i][1])

     情况二：

     有交集（a[i][0] <= r），左端点不变，更新右端点(r = max(r,a[i][1]))

  代码

  class Solution 
  {
  public:
      vector> merge(vector>& a) 
      {
          vector> v;
          if(a.empty()) return v;
          sort(a.begin(), a.end());
          int l = a[0][0], r = a[0][1];
          for(int i = 1; i < a.size(); i++)
          {
              if(r < a[i][0]) 
              {
                  v.push_back({l, r});
                  l = a[i][0], r = a[i][1];
              }
              else r = max(r,a[i][1]);
          }
          v.push_back({l, r});
          return v;
      }
  };