本文共 2501 字，大约阅读时间需要 8 分钟。

区间问题

1、区间的交集

1.1、题目

给定两个由一些 闭区间 组成的列表，每个区间列表都是成对不相交的，并且已经排序。

返回这两个区间列表的交集。

（形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x<= b。两个闭区间的交集是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3]。）

输入：A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

提示：

0 <= A.length < 1000

0 <= B.length < 1000 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

1.2、思路

1、没有交集

首先，对于两个区间，我们用 [a1,a2] 和 [b1,b2] 表示在 A 和 B 中的两个区间，那么什么情况下这两个区间没有交集呢：

if b2 < a1 || a2 < b1:    [a1,a2] 和 [b1,b2] //无交集

2、存在交集

如果交集区间是 [c1,c2]，那么 c1=max(a1,b1)，c2=min(a2,b2)

while i < len(A) && j < len(B):    a1, a2 = A[i][0], A[i][1]    b1, b2 = B[j][0], B[j][1]    if b2 >= a1 && a2 >= b1:        res.push_back({
   max(a1, b1), min(a2, b2)});    # ...

1.3、题解

class Solution {
   public:    vector
   
    
     > intervalIntersection(vector
     
      
       >& A, vector
       
        
         >& B) { vector
         
          
           > res; int lenA = A.size(); int lenB = B.size(); if(lenA == 0 || lenB == 0) return res; int i = 0,j = 0; while(i < lenA && j < lenB) { int a1 = A[i][0],a2 = A[i][1]; int b1 = B[j][0],b2 = B[j][1]; if(a2 >= b1 && b2 >= a1) { res.push_back({ max(a1,b1),min(a2,b2)}); } if(a2 < b2) i++; else j++; } return res; }};
          
         
        
       
      
     
    
   

2、区间的并集

2.1、题目

给出一个区间的集合，请合并所有重叠的区间。

输入: [[1,3],[2,6],[8,10],[15,18]]输出: [[1,6],[8,10],[15,18]]解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].输入: [[1,4],[4,5]]输出: [[1,5]]解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

2.2、思路

一个区间可以表示为 [start, end]，而对于区间合并问题，其实按 end 和 start 排序都可以。

显然，对于几个相交区间合并后的结果区间 x，x.start 一定是这些相交区间中 start 最小的（已经排序过了，从小到大），x.end 一定是这些相交区间中 end 最大的，毕竟取并集，谁的end最大，覆盖的最广。

2.3、题解

class Solution {
   public:    vector
   
    
     > merge(vector
     
      
       >& intervals) {
           int len = intervals.size();        if(len < 2)            return intervals;                //对start排序，从小到大        sort(intervals.begin(),intervals.end(),        [](vector
       
        & A,vector
        
         & B)//lambda表达式 { return A[0] < B[0];//从小到大排序 }); vector
         
          
           > res; res.emplace_back(intervals[0]);//push第一个元素 for(int i = 1;i < len;i++)//从第二个开始和第一个判断 { while(intervals[i][0] <= res.back()[1])//intervals[i]开始小于res.back()结束 { if(intervals[i][1] > res.back()[1])//intervals[i]结束大于res.back()结束，对于并集来说，谁的end更大，并集的范围也更大 res.back()[1] = intervals[i][1]; i++; if(i == len) return res; } res.emplace_back(intervals[i]);//没有重合部分，所以不用融合在一起 } return res; }};
          
         
        
       
      
     
    
   

转载地址：http://spuiz.baihongyu.com/