2026-09-30：筛选忙碌区间。用go语言，有一个整数数组，给定一个二维整数数组 occupiedIntervals，数组中的每一项 [starti, endi] 表示一|复杂度|log|spiderlinebreak|occupiedintervals

2026-09-30：筛选忙碌区间。用go语言，有一个整数数组，给定一个二维整数数组 occupiedIntervals，数组中的每一项 [starti, endi] 表示一

2026-09-30 01:24:33　来源: moonfdd

北京举报

分享至

2026-09-30：筛选忙碌区间。用go语言，有一个整数数组，给定一个二维整数数组 occupiedIntervals，数组中的每一项 [starti, endi] 表示一段忙碌时间。每段忙碌时间都把起点和终点算在内，并且不同忙碌时间段之间可能相互重叠。

另外给定两个整数 freeStart 和 freeEnd，表示一段空闲时间，这段空闲时间同样把起点和终点都算在内。

处理过程如下：

先把所有忙碌时间段中互相重叠或者刚好首尾相连的部分合并起来。所谓刚好首尾相连，是指某一段的终点加一，正好等于另一段的起点。例如 [1, 1] 和 [2, 2] 要合并成 [1, 2]。

合并完成后，再把空闲时间 [freeStart, freeEnd] 覆盖到的所有整数时间点，从合并后的忙碌时间中全部去掉。

去掉之后，把仍然处于忙碌状态的整数点重新整理成尽量少的连续区间，并按照区间起点从小到大排列。输出结果中的各个区间之间不能重叠。如果所有忙碌整数点都被去掉了，就返回空列表。

1 <= occupiedIntervals.length <= 50000。

occupiedIntervals[i].length == 2。

1 <= starti <= endi <= 1000000000。
1 <= freeStart <= freeEnd <= 1000000000。

输入： occupiedIntervals = [[2,6],[4,8],[10,10],[10,12],[14,16]], freeStart = 7, freeEnd = 11。

输出： [[2,6],[12,12],[14,16]]。

解释：

合并后，忙碌区间为 [2, 8]、[10, 12] 和 [14, 16]。

排除空闲区间 [7, 11] 后，得到 [2, 6]、[12, 12] 和 [14, 16]。

题目来自力扣3975。

处理过程详解 1. 先对所有忙碌区间排序

给定若干个忙碌时间段，每个区间用[start, end]表示，并且起点和终点都算在内。

第一步是按照每个忙碌区间的左端点从小到大排序。这样做的目的是让后续扫描时，所有区间都按照时间先后顺序排列，方便从左到右合并重叠或连续的区间。

2. 扫描并合并忙碌区间

排序后，从左到右依次扫描每个忙碌区间。扫描过程中维护一个“当前正在合并的忙碌段”，记它的左端点为left，右端点为right。

对于每个忙碌区间：

• 用当前区间的左端点更新left，取更小值；
• 用当前区间的右端点更新right，取更大值；
• 然后判断当前合并段是否应该结束。

判断规则是：

• 如果当前已经是最后一个区间，则当前合并段结束；
• 否则看下一个区间的左端点。
- • 如果下一个区间的左端点 - 1 > right，说明下一个区间与当前合并段之间至少隔了一个整数点，既不重叠，也不满足“首尾相连”，因此当前合并段结束；
- • 否则，说明下一个区间与当前合并段有重叠，或者刚好首尾相连，例如当前段是[1, 1]，下一段是[2, 2]，因为2 - 1 = 1，满足连续条件，所以继续合并。

当一段合并结束时，就得到了一个合并后的忙碌区间[left, right]。
例如题目中的忙碌区间：

[[2,6], [4,8], [10,10], [10,12], [14,16]]

合并后会得到：

[2,8]、[10,12]、[14,16]

其中[2,6]和[4,8]有重叠，合并为[2,8]；
[10,10]和[10,12]有重叠，合并为[10,12]；
[14,16]独立。

3. 用空闲区间去掉被覆盖的整数点

合并完成后，对于每一个合并后的忙碌区间[left, right]，再与空闲区间[freeStart, freeEnd]做差，也就是把空闲区间覆盖到的整数时间点从忙碌区间中去掉。

处理时分为几种情况：

情况一：完全不相交

• 如果right < freeStart，说明这个忙碌区间完全在空闲区间左边，不受影响，整个[left, right]保留；
• 如果left > freeEnd，说明这个忙碌区间完全在空闲区间右边，也不受影响，整个[left, right]保留。

情况二：有交集

如果忙碌区间与空闲区间有交集，则空闲区间会覆盖中间一部分，需要保留两边的剩余部分：

• 如果left < freeStart，说明忙碌区间左侧超出了空闲区间，那么左边剩余部分[left, freeStart - 1]仍然是忙碌的，加入结果；
• 如果right > freeEnd，说明忙碌区间右侧超出了空闲区间，那么右边剩余部分[freeEnd + 1, right]仍然是忙碌的，加入结果；
• 如果整个忙碌区间都被空闲区间覆盖，也就是left >= freeStart且right <= freeEnd，则这个忙碌区间完全被去掉，不产生任何结果。

以题目为例：

• 合并后的忙碌区间是[2,8]、[10,12]、[14,16]；
• 空闲区间是[7,11]。

逐个处理：

•[2,8]与[7,11]有交集。
左边超出部分：[2, 6]保留；
右边没有超出，所以不保留后缀。
得到[2,6]。
•[10,12]与[7,11]有交集。
左边没有超出；
右边超出部分：[12, 12]保留。
得到[12,12]。
•[14,16]完全在空闲区间右边，即left > freeEnd，所以整个保留。
得到[14,16]。

最终结果是：

[[2,6], [12,12], [14,16]]

4. 结果整理

由于之前合并后的忙碌区间本来就是按左端点从小到大产生的，所以做差后得到的剩余忙碌片段也天然按照起点从小到大排列，并且彼此之间不会重叠。

如果所有忙碌点都被空闲区间覆盖掉了，那么结果列表就是空的，直接返回空列表即可。

复杂度分析时间复杂度

• 排序所有忙碌区间：O(n log n)，其中n是occupiedIntervals的长度；
• 扫描并合并区间：每个区间只处理一次，O(n)；
• 对每个合并后的区间与空闲区间做差：同样是线性处理，O(n)。

所以总时间复杂度为：

O(n log n)

额外空间复杂度

• 结果数组ans最多可能保存O(n)个区间，因此如果计入返回结果，总额外空间为O(n)；
• 排序过程可能使用O(log n)的递归栈空间；
• 如果不把返回结果算作额外空间，则辅助空间主要是排序带来的O(log n)，其余扫描变量为常数级。

因此可以表述为：

• 总额外空间复杂度：O(n)（主要来自结果数组）；
• 若不计返回结果，辅助空间复杂度：O(log n)。

Go完整代码如下：

package main

 import (
    "fmt"
    "math"
    "slices"
)

 func filterOccupiedIntervals(occupiedIntervals [][]int, freeStart int, freeEnd int) (ans [][]int) {
    slices.SortFunc(occupiedIntervals, func(a, b []int)int { return a[0] - b[0] }) // 按照左端点从小到大排序

     left, right := math.MaxInt, 0
    for i, p := range occupiedIntervals {
        left = min(left, p[0])
        right = max(right, p[1])
        if i == len(occupiedIntervals)-1 || occupiedIntervals[i+1][0]-1 > right {
            if right < freeStart || left > freeEnd { // 不相交
                ans = append(ans, []int{left, right})
            } else {
                if left < freeStart {
                    ans = append(ans, []int{left, freeStart - 1}) // 余留前缀
                }
                if right > freeEnd {
                    ans = append(ans, []int{freeEnd + 1, right}) // 余留后缀
                }
            }
            left = math.MaxInt
        }
    }

     return
}

 func main() {
    occupiedIntervals := [][]int{{2, 6}, {4, 8}, {10, 10}, {10, 12}, {14, 16}}
    freeStart := 7
    freeEnd := 11
    result := filterOccupiedIntervals(occupiedIntervals, freeStart, freeEnd)
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 from typing import List

 def filterOccupiedIntervals(occupiedIntervals: List[List[int]], freeStart: int, freeEnd: int) -> List[List[int]]:
    occupiedIntervals.sort(key=lambda x: x[0])  # 按照左端点从小到大排序

     ans = []
    left = float('inf')
    right = 0

     for i, p in enumerate(occupiedIntervals):
        left = min(left, p[0])
        right = max(right, p[1])

         if i == len(occupiedIntervals) - 1 or occupiedIntervals[i + 1][0] - 1 > right:
            if right < freeStart or left > freeEnd:  # 不相交
                ans.append([left, right])
            else:
                if left < freeStart:
                    ans.append([left, freeStart - 1])  # 余留前缀
                if right > freeEnd:
                    ans.append([freeEnd + 1, right])  # 余留后缀
            left = float('inf')

     return ans

 if __name__ == "__main__":
    occupiedIntervals = [[2, 6], [4, 8], [10, 10], [10, 12], [14, 16]]
    freeStart = 7
    freeEnd = 11
    result = filterOccupiedIntervals(occupiedIntervals, freeStart, freeEnd)
    print(result)

C++完整代码如下：

  

  

    


 using namespace std;

 vector 
 
 int 
 >> filterOccupiedIntervals(vector 
 
 int 
 >> occupiedIntervals,  
 int 
  freeStart,  
 int 
  freeEnd) { 
 
 
      
 // 按照左端点从小到大排序 
 
 
     sort(occupiedIntervals.begin(), occupiedIntervals.end(), []( 
 const 
  vector< 
 int 
 >& a,  
 const 
  vector< 
 int 
 >& b) { 
 
 
          
 return 
  a[ 
 0 
 ] < b[ 
 0 
 ]; 
 
 
     }); 
 
 
 
 
     vector 
 
 int 
 >> ans; 
 
 
      
 int 
  left = INT_MAX; 
 
 
      
 int 
  right =  
 0 
 ; 
 
 
 
 
      
 for 
  ( 
 int 
  i =  
 0 
 ; i < ( 
 int 
 )occupiedIntervals.size(); ++i) { 
 
 
          
 const 
  auto& p = occupiedIntervals[i]; 
 
 
         left = min(left, p[ 
 0 
 ]); 
 
 
         right = max(right, p[ 
 1 
 ]); 
 
 
 
 
          
 if 
  (i == ( 
 int 
 )occupiedIntervals.size() -  
 1 
  || occupiedIntervals[i +  
 1 
 ][ 
 0 
 ] -  
 1 
  > right) { 
 
 
              
 if 
  (right < freeStart || left > freeEnd) {  
 // 不相交 
 
 
                 ans.push_back({left, right}); 
 
 
             }  
 else 
  { 
 
 
                  
 if 
  (left < freeStart) { 
 
 
                     ans.push_back({left, freeStart -  
 1 
 });  
 // 余留前缀 
 
 
                 } 
 
 
                  
 if 
  (right > freeEnd) { 
 
 
                     ans.push_back({freeEnd +  
 1 
 , right});  
 // 余留后缀 
 
 
                 } 
 
 
             } 
 
 
             left = INT_MAX; 
 
 
         } 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> occupiedIntervals = {{ 
 2 
 ,  
 6 
 }, { 
 4 
 ,  
 8 
 }, { 
 10 
 ,  
 10 
 }, { 
 10 
 ,  
 12 
 }, { 
 14 
 ,  
 16 
 }}; 
 
 
      
 int 
  freeStart =  
 7 
 ; 
 
 
      
 int 
  freeEnd =  
 11 
 ; 
 
 
     vector 
 
 int 
 >> result = filterOccupiedIntervals(occupiedIntervals, freeStart, freeEnd); 
 
 
 
 
     cout <<  
 "[" 
 ; 
 
 
      
 for 
  (size_t i =  
 0 
 ; i < result.size(); ++i) { 
 
 
          
 if 
  (i >  
 0 
 ) cout <<  
 ", " 
 ; 
 
 
         cout <<  
 "[" 
  << result[i][ 
 0 
 ] <<  
 ", " 
  << result[i][ 
 1 
 ] <<  
 "]" 
 ; 
 
 
     } 
 
 
     cout <<  
 "]" 
  << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 }

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。

特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.