在Python中编写用于计算完全包含在其他区间内的区间数字的程序

在很多应用场景中，我们需要对区间进行计算，例如：求两个区间的并集、交集或补集。与此同时，还有一种很重要的计算是，找出完全包含在其他区间内的区间，也就是子区间。本篇文章就是要探讨如何在Python中编写一个用于计算子区间的程序。

问题

假设我们有一个区间列表，其中每个元素代表一个区间，其格式如下所示：

interval_list = [(2, 5), (1, 9), (3, 8), (6, 10), (8, 11), (12, 18)]

现在，我们要计算其中所有完全被包含在其他区间内的区间。对于上面的区间列表，正确的结果应该是：

[(3, 5), (8, 8)]

解决方案

一种简单的做法是循环遍历区间列表，对于每个区间，判断它是否被其他区间所包含。但是这种做法的时间复杂度非常高，是 $O(n^3)$ 的，因为我们需要对每个区间进行两次比较。

如果我们想要更高效的解决方案，我们需要先将区间按照左边界排序，然后使用两个指针遍历区间列表。指针的初始位置都在区间列表的第一个元素。接着，我们比较指针所指向的区间是否满足完全被其他区间所包含的条件。如果当前区间被其他区间所包含，则将指针向右移动一个单位；否则，将右指针向右移动一个单位。我们反复执行这个过程，直到左指针到达区间列表的最后一个元素。下面是一个详细的示例代码：

def find_sub_intervals(interval_list):
    interval_list.sort()
    left = right = 0
    result = []
    while left < len(interval_list):
        if right == len(interval_list):
            left += 1
            right = left
            continue
        if interval_list[left][0] <= interval_list[right][0] and interval_list[left][1] >= interval_list[right][1]:
            if left != right:
                right += 1
        else:
            right += 1
        if right - left == len(interval_list) - 1:
            if left != right:
                result.append(interval_list[left])
            left += 1
            right = left
    return result

上面这段代码的主要思路是将区间按照左边界排序，然后使用两个指针遍历区间列表，找出所有完全被包含在其他区间内的区间。请注意，在执行前面的判断时，我们还特判了一下两个指针所指向的区间是否相等的情况。这是因为，如果我们没有加这个特判的话，程序在计算最后一个被包含在其他区间内的区间时会抛出一个“IndexError”的异常。

性能评估

为了评估我们的算法，在本章节中，我们将对不同规模的区间列表执行10次实验，记录每次实验的执行时间，然后求平均值。下面的代码展示了如何实现这个过程：

import time

def test(n):
    interval_list = [(i, i + 10) for i in range(n)]
    start = time.time()
    find_sub_intervals(interval_list)
    end = time.time()
    return end - start

for n in [10, 100, 1000, 10000]:
    total_time = 0
    for i in range(10):
        total_time += test(n)
    print("Average time for {:d} intervals: {:.6f} seconds".format(n, total_time / 10))

我们首先定义了一个test函数，该函数接受一个整数n作为参数，并在该区间内生成一组区间列表。接着，我们使用time.time()函数记录程序开始执行的时间，然后调用find_sub_intervals函数计算满足条件的子区间。最后，我们再次调用time.time()函数记录程序结束执行的时间，并返回二者之差。

在主函数中，我们首先定义了一个整数列表，其中包含4个元素：10、100、1000和10000。然后，我们遍历这个列表中的每个元素，在每个元素上运行10次实验，并计算出每次实验的平均执行时间。

下面的表格展示了实验结果：