Python 求解闭区间选点最小总成本问题：代码、解释与复杂度分析

以下是解决该问题的Python代码： ```python # 读取输入 n = int(input()) # 存储区间的列表 intervals = [] for _ in range(n): l, r = map(int, input().split()) intervals.append((l, r)) # 按照区间的右边界从小到大排序 intervals.sort(key=lambda x: x[1]) # 存储选择的点 selected_points = [] # 遍历每个区间 for l, r in intervals: # 检查是否已经有选择的点在当前区间内 found = False for point in selected_points: if l <= point <= r: found = True break # 如果没有找到点在当前区间内，则选择该区间的右边界作为新的点 if not found: selected_points.append(r) # 计算选择的点的总成本 total_cost = sum(selected_points) print(total_cost) ``` 代码解释： 1. 输入读取：首先读取区间的数量 `n`，然后循环 `n` 次，每次读取一个区间的左右边界，并将其存储在 `intervals` 列表中。 2. 区间排序：使用 `sort` 方法按照区间的右边界从小到大对 `intervals` 列表进行排序。这样做的目的是优先选择右边界较小的区间，因为选择右边界的点可以覆盖尽可能多的后续区间。 3. 选择点：遍历排序后的区间列表，对于每个区间，检查是否已经有选择的点在该区间内。如果没有，则选择该区间的右边界作为新的点，并将其添加到 `selected_points` 列表中。 4. 计算总成本：使用 `sum` 函数计算 `selected_points` 列表中所有点的总和，并将其作为最小总成本输出。 复杂度分析： - 时间复杂度：排序操作的时间复杂度为 $O(n log n)$，遍历区间列表的时间复杂度为 $O(n^2)$，因此总的时间复杂度为 $O(n^2)$。 - 空间复杂度：主要使用了 `intervals` 和 `selected_points` 两个列表，空间复杂度为 $O(n)$。 ######[AI问答 | 500点数解答 | 2025-12-13 10:58:42]