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)。
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 ansif __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助力您的未来发展。
热门跟贴