如何降低AoC区间包含问题的时间复杂度？

问题描述 #

给定如下数据：

data = """2-4,6-8
    2-3,4-5
    5-7,7-9
    2-8,3-7
    6-6,4-6
    2-6,4-8"""

需求是统计其中完全包含另一区间的区间对数量。例如：

• 2-8完全包含3-7
• 6-6被4-6完全包含

原始暴力解法 #

以下是已实现的暴力解法代码：

def aoc_part1(self, data):
    counter = 0
    for lines_data in data.splitlines():
        lines_data = lines_data.strip()
        first_range, second_range = self.__get_first_second_list_of_elements(lines_data)
        check_first_side_if_returns_true = all(item in first_range for item in second_range)
        check_second_side_if_returns_true = all(item in second_range for item in first_range)
        if check_first_side_if_returns_true or check_second_side_if_returns_true:
            counter += 1
    return counter

def __get_first_second_list_of_elements(self, data):
    first_elf, second_elf = data.split(",")[0], data.split(",")[1]
    first_range_start, first_range_end = map(int, first_elf.split("-"))
    second_range_start, second_range_end = map(int, second_elf.split("-"))
    first_range = list(range(first_range_start, first_range_end + 1))
    second_range = list(range(second_range_start, second_range_end + 1))
    return first_range, second_range

疑问 #

上述解法属于暴力破解，每次迭代中all会触发额外循环，时间复杂度较高。请问如何将该方案优化至线性时间复杂度？

优化方案 #

核心思路：用区间起止点直接判断包含关系 #

不需要生成完整的区间列表，也不需要遍历区间内的所有元素。对于两个区间[a1, a2]和[b1, b2]，满足完全包含的条件只需判断：

• 区间A完全包含区间B：a1 ≤ b1 且 a2 ≥ b2
• 区间B完全包含区间A：b1 ≤ a1 且 b2 ≥ a2

只要满足其中一个条件，即可判定这对区间符合要求。

优化后的代码 #

def aoc_part1(self, data):
    counter = 0
    for line in data.splitlines():
        line = line.strip()
        if not line:
            continue  # 跳过空行
        # 解析两个区间的起止点
        left, right = line.split(",")
        a1, a2 = map(int, left.split("-"))
        b1, b2 = map(int, right.split("-"))
        # 判断完全包含关系
        if (a1 <= b1 and a2 >= b2) or (b1 <= a1 and b2 >= a2):
            counter += 1
    return counter

复杂度分析 #

• 时间复杂度：O(n)，其中n是数据的行数。每行仅执行固定次数的字符串分割、类型转换和比较操作，无嵌套循环。
• 空间复杂度：O(1)，仅使用少量变量存储起止点和计数器，无需生成区间列表。

对比原始解法的优势 #

1. 避免了大区间列表的内存开销（比如区间是1-100000时，原始解法会生成10万个元素的列表，优化后仅用4个整数）
2. 彻底消除嵌套循环，时间复杂度从O(n*m)（m为区间平均长度）降至O(n)，性能提升显著

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