如何通过通用循环计算覆盖街道区间所需的最少交通灯数量

核心实现逻辑 #

你需要的按选择数量从小到大枚举任意k个元素的组合，不需要写k层循环，直接用Python标准库itertools.combinations即可实现，它可以自动生成指定数量的所有不重复组合，完美适配任意大小的输入数组。

1. 预处理步骤 #

首先对输入的lights数组做预处理，过滤无效灯、裁剪覆盖区间到[0, n]范围内，减少后续计算量：

• 每个灯的原始覆盖区间是[pos - strength, pos + strength]
• 裁剪为有效区间[max(0, pos - strength), min(n, pos + strength)]
• 如果有效区间的左端点 > 右端点，说明这个灯完全覆盖不到街道，直接丢弃

2. 区间覆盖检查函数 #

输入一组区间，判断它们的并集是否能完整覆盖[0, n]，比你原来用数组逐个标记的方案效率高很多，也适配任意大小的n：

• 先把所有区间按左端点从小到大排序
• 初始化当前覆盖到的最右位置为0
• 遍历排序后的区间，只要当前区间的左端点 <= 当前覆盖最右位置，就更新当前覆盖最右位置为max(当前覆盖最右, 区间右端点)
• 遍历完成后如果当前覆盖最右 >= n，说明覆盖完整，否则不满足

3. 按k从小到大枚举组合 #

k从1开始，到预处理后灯的总数量为止：

• 对每个k，生成所有k个灯的组合
• 对每个组合，调用上面的检查函数判断是否满足覆盖要求
• 只要有一个组合满足，直接返回当前的k值，就是最小值
• 所有k遍历完都没有满足的组合，返回-1

完整代码实现 #

import itertools

def check_cover(intervals, n):
    # 按区间左端点排序
    intervals.sort()
    current_right = 0
    idx = 0
    length = len(intervals)
    while current_right < n and idx < length:
        # 当前区间左端点超过已覆盖最右，存在缺口无法覆盖
        if intervals[idx][0] > current_right:
            return False
        # 更新已覆盖的最右位置
        current_right = max(current_right, intervals[idx][1])
        idx += 1
    return current_right >= n

def min_lights(n, lights):
    # 预处理所有灯的有效区间
    valid_intervals = []
    for pos, strength in lights:
        left = max(0, pos - strength)
        right = min(n, pos + strength)
        if left <= right:
            valid_intervals.append((left, right))
    total = len(valid_intervals)
    # 按选择的灯数量从小到大枚举
    for k in range(1, total + 1):
        # 生成所有k个灯的组合
        for combo in itertools.combinations(valid_intervals, k):
            if check_cover(list(combo), n):
                return k
    # 所有组合都不满足
    return -1

# 测试示例1
n1 = 10
lights1 = [[0,5],[1,3],[5,4],[8,3]]
print(min_lights(n1, lights1)) # 输出2

# 测试示例2
n2 = 10
lights2 = [[0,4],[0,5],[5,10],[1,9]]
print(min_lights(n2, lights2)) # 输出1，单个[1,9]即可覆盖全区间

优化说明 #

• 如果灯的数量超过20，组合枚举的时间复杂度会急剧上升，此时建议换成经典的区间覆盖贪心算法，时间复杂度可以降到O(m log m)（m是灯的数量），适配更大规模的输入
• 可以提前对有效区间去重，相同的区间只保留一个，减少组合枚举的数量

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