如何用Python实现无库依赖的最少线段路径求解？

问题背景 #

给定起点、终点和线段列表：

start = 10
end = 100
li = [(50, 60), (10, 20), (10, 40), (40, 60), (60, 80), (75, 95), (95, 100), (35, 45)]

需要实现Python代码，找到从起点到终点所需的最少线段数量；如果线段不足无法到达，程序要给出提示。要求不能使用任何库或import语句，尽可能降低时间与内存消耗。

我自己写了一段低效代码：

for el in li:
    for el1 in li:
        if el != el1 and el[0] >= el1[0] and el[1] <= el1[1]:
            li.remove(el)

        elif el != el1 and (el[1] == el1[0] or el[0] == el1[1]):
            tmp = (min(el[0], el1[0]), max(el[1], el[1]))

            for el2 in li:
                if el != el2 and el1 != el2 and el2[0] >= tmp[0] and el2[1] <= tmp[1]:
                    li.remove(el2)

这段代码有三层嵌套循环，而且第三层循环里还做了remove操作，运行效率特别低，求优化方案。

优化方案：贪心算法 #

要找最少线段数，贪心算法是最优选择——每次在当前能到达的范围内，选终点最远的线段，这样能覆盖最大的范围，用最少的步数到达终点。

具体步骤 #

• 预处理线段：先过滤掉无效线段（比如起点大于终点的，这类线段完全没用），然后把剩下的线段按起点从小到大排序。
• 初始化变量：设置当前到达位置、下一步最远可达位置、已用线段数、遍历索引等参数。
• 循环遍历：在当前覆盖范围内，不断更新最远可达位置；如果无法前进则提示不可达，若已覆盖终点则输出最少线段数。

优化后的代码 #

start = 10
end = 100
li = [(50, 60), (10, 20), (10, 40), (40, 60), (60, 80), (75, 95), (95, 100), (35, 45)]

# 预处理：过滤无效线段，手动按起点排序
filtered_segments = []
for seg in li:
    if seg[0] <= seg[1]:
        filtered_segments.append(seg)

# 冒泡排序（无库实现）
n = len(filtered_segments)
for i in range(n):
    for j in range(0, n-i-1):
        if filtered_segments[j][0] > filtered_segments[j+1][0]:
            filtered_segments[j], filtered_segments[j+1] = filtered_segments[j+1], filtered_segments[j]

current_pos = start
max_reach = start
steps = 0
index = 0
seg_count = len(filtered_segments)

while current_pos < end:
    # 寻找当前范围内终点最远的线段
    while index < seg_count and filtered_segments[index][0] <= current_pos:
        if filtered_segments[index][1] > max_reach:
            max_reach = filtered_segments[index][1]
        index += 1
    
    # 无法继续前进，输出提示
    if max_reach == current_pos:
        print("无法从起点到达终点")
        break
    
    steps += 1
    current_pos = max_reach
    
    # 已到达终点，输出结果
    if current_pos >= end:
        print(f"最少需要{steps}条线段")
        break

优化点说明 #

• 时间效率：排序用O(n²)的冒泡排序（小数据量足够高效，大数据量可替换为快速排序），遍历仅O(n)，整体复杂度远低于原代码的O(n³)。
• 内存消耗：仅额外存储过滤后的线段列表，避免了原代码中频繁remove带来的列表扩容缩容开销。
• 逻辑简洁：直接瞄准“最少线段”的核心需求，无需复杂的嵌套循环和线段合并操作。

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