基于可用/不可用时间字典生成有效时段的优化方案问询

我有多个实体，每个实体的可用时间和不可用时间分别存储在两个列表中，不可用时间优先级高于可用时间。例如某实体可用时段为[1,5]、[8,15]，不可用时段为[2,4]、[7,9]、[11,13]，则实际可用时段为[1,2]、[4,5]、[9,11]、[13,15]。

单个实体的示例数据如下：

time_dict = {
    'available': [[7590, 8280], [9030, 9720], [10470, 11160], [11910, 12600], [20550, 21240], [21990, 22680], [23430, 24120], [24870, 25560], [26310, 27000], [33510, 34200], [34950, 35640], [36390, 37080], [37830, 38520], [39270, 39960]],
    'not_available': [[7740, 7755], [7920, 7950], [8100, 8115], [9180, 9195], [9360, 9390], [9540, 9555], [10620, 10635], [10800, 10830], [10980, 10995], [12060, 12075], [12240, 12270], [12420, 12435], [20700, 20715], [20880, 20910], [21060, 21075], [22140, 22155], [22320, 22350], [22500, 22515], [23580, 23595], [23760, 23790], [23940, 23955], [25020, 25035], [25200, 25230], [25380, 25395], [26460, 26475], [26640, 26670], [26820, 26835], [33660, 33675], [33840, 33870], [34020, 34035], [35100, 35115], [35280, 35310], [35460, 35475], [36540, 36555], [36720, 36750], [36900, 36915], [37980, 37995], [38160, 38190], [38340, 38355], [39420, 39435], [39600, 39630], [39780, 39795]]
}

我当前用嵌套循环生成实际可用时段，代码如下：

available_slots = []

for available in time_dict['available']:
    start, end = available
    not_available = [d for d in time_dict['not_available'] if d[0] < end and d[1] > start]

    if not not_available:
        available_slots.append(available)
    else:
        prev_end = start
        for i in not_available:
            if i[0] > prev_end:
                available_slots.append([prev_end, i[0]])
            prev_end = i[1]
        if prev_end < end:
            available_slots.append([prev_end, end])

print("Available Slots:", available_slots)

该方法可实现需求，但效率较低，且需对每个实体重复执行，会产生多层嵌套循环。请问是否存在更高效的实现方式？

高效实现方案 #

核心思路是先对可用时段和不可用时段按起始时间排序，再用双指针法遍历两个列表，避免嵌套循环中的重复筛选，时间复杂度从O(M*N)降至O(M+N)（M为可用时段数量，N为不可用时段数量）。

步骤说明 #

1. 排序预处理：确保可用时段、不可用时段按起始时间升序排列（示例数据已排序，但通用场景需处理未排序的情况）。
2. 双指针遍历：用两个指针分别指向当前处理的可用时段和不可用时段，逐个匹配重叠的不可用时段，切割出实际可用区间。

代码实现 #

def calculate_actual_available(available, not_available):
    # 对时段按起始时间排序（处理未排序的原始数据）
    available_sorted = sorted(available, key=lambda x: x[0])
    not_available_sorted = sorted(not_available, key=lambda x: x[0])
    
    actual_available = []
    avail_ptr = 0  # 可用时段指针
    na_ptr = 0     # 不可用时段指针
    num_avail = len(available_sorted)
    num_na = len(not_available_sorted)
    
    while avail_ptr < num_avail:
        current_avail_start, current_avail_end = available_sorted[avail_ptr]
        current_start = current_avail_start
        
        # 遍历所有与当前可用时段重叠的不可用时段
        while na_ptr < num_na:
            na_start, na_end = not_available_sorted[na_ptr]
            
            # 不可用时段在当前可用时段结束后，停止匹配
            if na_start >= current_avail_end:
                break
            
            # 不可用时段在当前可用时段开始前，直接跳过
            if na_end <= current_avail_start:
                na_ptr += 1
                continue
            
            # 切割出可用区间
            if na_start > current_start:
                actual_available.append([current_start, na_start])
            
            # 更新当前可用起始点为不可用时段的结束时间
            current_start = max(current_start, na_end)
            na_ptr += 1
        
        # 处理当前可用时段剩余的未被占用部分
        if current_start < current_avail_end:
            actual_available.append([current_start, current_avail_end])
        
        avail_ptr += 1
    
    return actual_available

# 调用示例
time_dict = {
    'available': [[7590, 8280], [9030, 9720], [10470, 11160], [11910, 12600], [20550, 21240], [21990, 22680], [23430, 24120], [24870, 25560], [26310, 27000], [33510, 34200], [34950, 35640], [36390, 37080], [37830, 38520], [39270, 39960]],
    'not_available': [[7740, 7755], [7920, 7950], [8100, 8115], [9180, 9195], [9360, 9390], [9540, 9555], [10620, 10635], [10800, 10830], [10980, 10995], [12060, 12075], [12240, 12270], [12420, 12435], [20700, 20715], [20880, 20910], [21060, 21075], [22140, 22155], [22320, 22350], [22500, 22515], [23580, 23595], [23760, 23790], [23940, 23955], [25020, 25035], [25200, 25230], [25380, 25395], [26460, 26475], [26640, 26670], [26820, 26835], [33660, 33675], [33840, 33870], [34020, 34035], [35100, 35115], [35280, 35310], [35460, 35475], [36540, 36555], [36720, 36750], [36900, 36915], [37980, 37995], [38160, 38190], [38340, 38355], [39420, 39435], [39600, 39630], [39780, 39795]]
}

actual_slots = calculate_actual_available(time_dict['available'], time_dict['not_available'])
print("实际可用时段:", actual_slots)

效率优势 #

• 原方法中，每个可用时段都需遍历所有不可用时段做筛选，时间复杂度为O(M*N)，数据量较大时（如上千个时段）性能会急剧下降。
• 新方法通过排序（O(M log M + N log N)）加双指针遍历（O(M+N)），整体时间复杂度远低于原方法，尤其适合多实体的批量计算场景。

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