企业官网建设流程全解析

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完整代码如下：

packagemainimport("fmt""math""slices")funcfilterOccupiedIntervals(occupiedIntervals[][]int,freeStartint,freeEndint)(ans[][]int){slices.SortFunc(occupiedIntervals,func(a,b[]int)int{returna[0]-b[0]})// 按照左端点从小到大排序left,right:=math.MaxInt,0fori,p:=rangeoccupiedIntervals{left=min(left,p[0])right=max(right,p[1])ifi==len(occupiedIntervals)-1||occupiedIntervals[i+1][0]-1>right{ifright<freeStart||left>freeEnd{// 不相交ans=append(ans,[]int{left,right})}else{ifleft<freeStart{ans=append(ans,[]int{left,freeStart-1})// 余留前缀}ifright>freeEnd{ans=append(ans,[]int{freeEnd+1,right})// 余留后缀}}left=math.MaxInt}}return}funcmain(){occupiedIntervals:=[][]int{{2,6},{4,8},{10,10},{10,12},{14,16}}freeStart:=7freeEnd:=11result:=filterOccupiedIntervals(occupiedIntervals,freeStart,freeEnd)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-fromtypingimportListdeffilterOccupiedIntervals(occupiedIntervals:List[List[int]],freeStart:int,freeEnd:int)->List[List[int]]:occupiedIntervals.sort(key=lambdax:x[0])# 按照左端点从小到大排序ans=[]left=float('inf')right=0fori,pinenumerate(occupiedIntervals):left=min(left,p[0])right=max(right,p[1])ifi==len(occupiedIntervals)-1oroccupiedIntervals[i+1][0]-1>right:ifright<freeStartorleft>freeEnd:# 不相交ans.append([left,right])else:ifleft<freeStart:ans.append([left,freeStart-1])# 余留前缀ifright>freeEnd:ans.append([freeEnd+1,right])# 余留后缀left=float('inf')returnansif__name__=="__main__":occupiedIntervals=[[2,6],[4,8],[10,10],[10,12],[14,16]]freeStart=7freeEnd=11result=filterOccupiedIntervals(occupiedIntervals,freeStart,freeEnd)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;vector<vector<int>>filterOccupiedIntervals(vector<vector<int>>occupiedIntervals,intfreeStart,intfreeEnd){// 按照左端点从小到大排序sort(occupiedIntervals.begin(),occupiedIntervals.end(),[](constvector<int>&a,constvector<int>&b){returna[0]<b[0];});vector<vector<int>>ans;intleft=INT_MAX;intright=0;for(inti=0;i<(int)occupiedIntervals.size();++i){constauto&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;}}returnans;}intmain(){vector<vector<int>>occupiedIntervals={{2,6},{4,8},{10,10},{10,12},{14,16}};intfreeStart=7;intfreeEnd=11;vector<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;return0;}