寻找模拟设备对应数字领域区间数组的空闲范围快速算法

核心逻辑 #

这类场景的最优解法是先排序合并已占用区间，再遍历计算间隙，整体时间复杂度为O(n log n)（主要来自排序），比暴力遍历每个点的效率高得多。如果原始区间存在重叠或相邻，必须先合并，否则会得出错误的可用区间。

算法步骤 #

1. 排序已占用区间：按区间的起始值从小到大排序。
2. 合并重叠/相邻区间：遍历排序后的区间，将重叠或首尾相连的区间合并为单个连续区间。
3. 计算可用区间：从指定的最小边界开始，依次对比已合并区间的首尾，中间的空隙即为可用区间；最后检查最大边界与最后一个合并区间的间隙。

Python 实现示例 #

def find_available_intervals(occupied_intervals, min_bound=0, max_bound=None):
    # 处理空输入
    if not occupied_intervals:
        return [(min_bound, max_bound)] if max_bound is not None else []
    
    # 1. 按区间起始值排序
    sorted_intervals = sorted(occupied_intervals, key=lambda x: x[0])
    
    # 2. 合并重叠/相邻区间
    merged = []
    current_start, current_end = sorted_intervals[0]
    for start, end in sorted_intervals[1:]:
        if start <= current_end:
            # 重叠或相邻则合并
            current_end = max(current_end, end)
        else:
            merged.append((current_start, current_end))
            current_start, current_end = start, end
    merged.append((current_start, current_end))
    
    # 3. 计算可用区间
    available = []
    # 第一个区间前的间隙
    if merged[0][0] > min_bound:
        available.append((min_bound, merged[0][0]))
    
    # 中间的间隙
    for i in range(1, len(merged)):
        prev_end = merged[i-1][1]
        curr_start = merged[i][0]
        if curr_start > prev_end:
            available.append((prev_end, curr_start))
    
    # 最后一个区间后的间隙（若指定了最大边界）
    if max_bound is not None and merged[-1][1] < max_bound:
        available.append((merged[-1][1], max_bound))
    
    return available

# 测试用例
occupied = [(1, 3), (5, 7), (2, 4), (8, 10)]
print(find_available_intervals(occupied, min_bound=0, max_bound=12))
# 输出: [(0, 1), (4, 5), (7, 8), (10, 12)]

PHP 实现示例 #

function findAvailableIntervals($occupiedIntervals, $minBound = 0, $maxBound = null) {
    // 处理空输入
    if (empty($occupiedIntervals)) {
        return $maxBound !== null ? [[$minBound, $maxBound]] : [];
    }
    
    // 1. 按区间起始值排序
    usort($occupiedIntervals, function($a, $b) {
        return $a[0] - $b[0];
    });
    
    // 2. 合并重叠/相邻区间
    $merged = [];
    list($currentStart, $currentEnd) = $occupiedIntervals[0];
    foreach (array_slice($occupiedIntervals, 1) as $interval) {
        list($start, $end) = $interval;
        if ($start <= $currentEnd) {
            $currentEnd = max($currentEnd, $end);
        } else {
            $merged[] = [$currentStart, $currentEnd];
            $currentStart = $start;
            $currentEnd = $end;
        }
    }
    $merged[] = [$currentStart, $currentEnd];
    
    // 3. 计算可用区间
    $available = [];
    // 第一个区间前的间隙
    if ($merged[0][0] > $minBound) {
        $available[] = [$minBound, $merged[0][0]];
    }
    
    // 中间的间隙
    for ($i = 1; $i < count($merged); $i++) {
        $prevEnd = $merged[$i-1][1];
        $currStart = $merged[$i][0];
        if ($currStart > $prevEnd) {
            $available[] = [$prevEnd, $currStart];
        }
    }
    
    // 最后一个区间后的间隙
    if ($maxBound !== null && $merged[count($merged)-1][1] < $maxBound) {
        $available[] = [$merged[count($merged)-1][1], $maxBound];
    }
    
    return $available;
}

// 测试用例
$occupied = [[1,3], [5,7], [2,4], [8,10]];
print_r(findAvailableIntervals($occupied, 0, 12));
// 输出: Array ( [0] => Array ( [0] => 0 [1] => 1 ) [1] => Array ( [0] => 4 [1] => 5 ) [2] => Array ( [0] => 7 [1] => 8 ) [3] => Array ( [0] => 10 [1] => 12 ) )

伪代码 #

FUNCTION find_available_intervals(occupied_intervals, min_bound, max_bound):
    IF occupied_intervals IS EMPTY:
        IF max_bound IS NOT NULL:
            RETURN [(min_bound, max_bound)]
        ELSE:
            RETURN EMPTY LIST
    
    SORT occupied_intervals BY the first element of each interval
    
    merged = EMPTY LIST
    current_start, current_end = first interval in occupied_intervals
    
    FOR EACH interval IN rest of occupied_intervals:
        start, end = interval
        IF start <= current_end:
            current_end = MAX(current_end, end)
        ELSE:
            ADD (current_start, current_end) TO merged
            current_start, current_end = start, end
    ADD (current_start, current_end) TO merged
    
    available = EMPTY LIST
    
    IF merged[0][0] > min_bound:
        ADD (min_bound, merged[0][0]) TO available
    
    FOR i FROM 1 TO LENGTH(merged)-1:
        prev_end = merged[i-1][1]
        curr_start = merged[i][0]
        IF curr_start > prev_end:
            ADD (prev_end, curr_start) TO available
    
    IF max_bound IS NOT NULL AND merged[-1][1] < max_bound:
        ADD (merged[-1][1], max_bound) TO available
    
    RETURN available

内容的提问来源于stack exchange，提问作者Ibiza