基于区间列表生成0/1索引标记列表的高效实现方法问询

问题背景 #

我现在有一个数值区间列表 intervals = [[1, 4], [7, 9], [13, 18]]，需要生成一个包含20个元素的列表：索引不在任何区间里就设为0，在任意区间内就设为1。预期输出是：
output = [0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0]

目前我写了一个基础实现：

output = [0] * 20
for index, _ in enumerate(output):
    for interval in intervals:
        if interval[0] <= index <= interval[1]:
            output[index] = 1

但感觉这个嵌套循环效率不高，想问问有没有更高效的实现方式？

高效解决方案 #

咱们先说说原方法的问题：它是**O(n*m)**的时间复杂度（n是输出列表长度，m是区间数量），每个索引都要遍历所有区间做判断，当n或m很大时，会浪费不少时间。下面两种方法能把复杂度降下来，效率提升明显：

1. Python原生高效实现（无依赖，适合通用场景）

思路是先合并重叠/相邻的区间（避免重复赋值），然后通过切片批量赋值来替代逐个索引判断，这样时间复杂度降到O(m log m)（排序区间的时间） + O(n)（赋值时间）。

def generate_marked_list(intervals, length):
    output = [0] * length
    if not intervals:
        return output
    
    # 先按区间起始位置排序，方便合并
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged_intervals = [sorted_intervals[0]]
    
    # 合并重叠或相邻的区间
    for current_start, current_end in sorted_intervals[1:]:
        last_start, last_end = merged_intervals[-1]
        if current_start <= last_end + 1:
            # 重叠或相邻，更新区间结束位置
            merged_intervals[-1] = [last_start, max(last_end, current_end)]
        else:
            merged_intervals.append([current_start, current_end])
    
    # 批量给区间内的索引赋值为1
    for start, end in merged_intervals:
        # 处理区间超出列表长度的情况
        start = max(start, 0)
        end = min(end, length - 1)
        if start > end:
            continue
        # 切片赋值比逐个循环快得多
        output[start:end+1] = [1] * (end - start + 1)
    
    return output

# 测试
intervals = [[1, 4], [7, 9], [13, 18]]
print(generate_marked_list(intervals, 20))

2. Numpy向量化实现（适合大数据量场景）

如果你的输出列表长度非常大（比如几万、几十万），用Numpy的向量化操作会快很多——因为Numpy的操作是在C层面执行的，避免了Python循环的开销。

import numpy as np

intervals = [[1, 4], [7, 9], [13, 18]]
length = 20

# 生成所有索引的数组
indices = np.arange(length)
# 初始化全0数组
output = np.zeros(length, dtype=int)

# 用布尔掩码标记所有区间内的索引
mask = np.zeros(length, dtype=bool)
for start, end in intervals:
    mask |= (indices >= start) & (indices <= end)

# 把掩码转成0-1列表
output = mask.astype(int).tolist()
print(output)

这个方法的核心是用布尔掩码批量标记，只需要一次最终赋值，比嵌套循环快几个数量级。

总结 #

• 如果是小数据量（比如示例中的length=20），几种方法差异不大，但大数据量下，上面两种高效方法的优势会非常明显。
• 原生方法不需要依赖第三方库，适合纯Python环境；Numpy方法则是大数据量场景的最优选择。

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