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(fmtmathslices)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{leftmin(left,p[0])rightmax(right,p[1])ifilen(occupiedIntervals)-1||occupiedIntervals[i1][0]-1right{ifrightfreeStart||leftfreeEnd{// 不相交ansappend(ans,[]int{left,right})}else{ifleftfreeStart{ansappend(ans,[]int{left,freeStart-1})// 余留前缀}ifrightfreeEnd{ansappend(ans,[]int{freeEnd1,right})// 余留后缀}}leftmath.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(keylambdax:x[0])# 按照左端点从小到大排序ans[]leftfloat(inf)right0fori,pinenumerate(occupiedIntervals):leftmin(left,p[0])rightmax(right,p[1])ifilen(occupiedIntervals)-1oroccupiedIntervals[i1][0]-1right:ifrightfreeStartorleftfreeEnd:# 不相交ans.append([left,right])else:ifleftfreeStart:ans.append([left,freeStart-1])# 余留前缀ifrightfreeEnd:ans.append([freeEnd1,right])# 余留后缀leftfloat(inf)returnansif__name____main__:occupiedIntervals[[2,6],[4,8],[10,10],[10,12],[14,16]]freeStart7freeEnd11resultfilterOccupiedIntervals(occupiedIntervals,freeStart,freeEnd)print(result)C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;vectorvectorintfilterOccupiedIntervals(vectorvectorintoccupiedIntervals,intfreeStart,intfreeEnd){// 按照左端点从小到大排序sort(occupiedIntervals.begin(),occupiedIntervals.end(),[](constvectorinta,constvectorintb){returna[0]b[0];});vectorvectorintans;intleftINT_MAX;intright0;for(inti0;i(int)occupiedIntervals.size();i){constautopoccupiedIntervals[i];leftmin(left,p[0]);rightmax(right,p[1]);if(i(int)occupiedIntervals.size()-1||occupiedIntervals[i1][0]-1right){if(rightfreeStart||leftfreeEnd){// 不相交ans.push_back({left,right});}else{if(leftfreeStart){ans.push_back({left,freeStart-1});// 余留前缀}if(rightfreeEnd){ans.push_back({freeEnd1,right});// 余留后缀}}leftINT_MAX;}}returnans;}intmain(){vectorvectorintoccupiedIntervals{{2,6},{4,8},{10,10},{10,12},{14,16}};intfreeStart7;intfreeEnd11;vectorvectorintresultfilterOccupiedIntervals(occupiedIntervals,freeStart,freeEnd);cout[;for(size_t i0;iresult.size();i){if(i0)cout, ;cout[result[i][0], result[i][1]];}cout]endl;return0;}