<think>我们有一个区间列表，例如：[(4.2, 16.0), (14.47, 28.8)]，需要合并重叠的区间。 合并重叠区间的思路： 1. 首先，按照每个区间的起始值进行排序。 2. 初始化一个结果列表，将第一个区间加入结果。 3. 遍历排序后的区间列表（从第二个区间开始）： a. 取出结果列表中最后一个区间的结束值（记为lastEnd）。 b. 当前区间的开始值（start）和结束值（end）。 c. 如果当前区间的开始值小于等于lastEnd，说明有重叠，则合并区间：将结果列表中最后一个区间的结束值更新为max(lastEnd, 当前区间的结束值)。 d. 如果没有重叠，则将当前区间加入结果列表。 注意：由于区间是浮点数，比较时需要注意浮点数的精度问题。但在一般情况下，我们可以直接比较。 对于给定的例子：[(4.2, 16.0), (14.47, 28.8)] 第一步排序：由于4.2<14.47，所以排序后不变。 第二步：将(4.2,16.0)加入结果。 第三步：遍历到(14.47,28.8)： lastEnd = 16.0 当前区间start=14.47，end=28.8 因为14.47<=16.0，所以合并区间：更新最后一个区间为(4.2, max(16.0,28.8)) -> (4.2, 28.8) 因此合并后为[(4.2, 28.8)] 我们根据上述思路编写代码。 但是注意：引用[1]中提供了一个合并区间的代码，但它是针对整数区间的，我们这里区间是浮点数，但算法相同。 我们参考引用[1]的代码，稍作调整（因为引用[1]的代码是用于合并区间，并且是整数，但浮点数同样适用）。 另外，注意输入区间是列表，每个区间是一个元组（或列表），例如：intervals = [(4.2, 16.0), (14.47, 28.8)] 代码实现如下： </think> ### Python合并重叠区间实现 以下是针对浮点数区间（如`[(4.2, 16.0), (14.47, 28.8)]`）的合并算法实现： ```python def merge_intervals(intervals): """ 合并重叠区间 :param intervals: 区间列表，格式 [(start1, end1), (start2, end2), ...] :return: 合并后的区间列表 """ if not intervals: return [] # 按区间起点排序 intervals.sort(key=lambda x: x[0]) merged = [intervals[0]] # 初始化结果列表 for current_start, current_end in intervals[1:]: last_start, last_end = merged[-1] # 取出结果中最后一个区间 # 检查重叠：当前区间起点 <= 上一个区间终点 if current_start <= last_end: # 合并区间：更新上一个区间的终点为较大值 merged[-1] = (last_start, max(last_end, current_end)) else: # 无重叠时直接添加新区间 merged.append((current_start, current_end)) return merged # 测试示例 intervals = [(4.2, 16.0), (14.47, 28.8)] result = merge_intervals(intervals) print(f"合并结果: {result}") # 输出: [(4.2, 28.8)] ``` #### 算法说明： 1. **排序预处理** 使用 `intervals.sort(key=lambda x: x[0])` 将所有区间按起点升序排列 *目的：确保后续只需单向检查重叠* 2. **合并逻辑** - 初始化合并列表为第一个区间 - 遍历后续每个区间： - 若当前区间起点 $≤$ 上一个区间的终点：扩展合并区间的终点 $$ \text{merged}[-1] = (\text{last\_start}, \max(\text{last\_end}, \text{current\_end})) $$ - 否则：作为新区间加入结果列表 3. **浮点数处理** 算法直接支持浮点数区间，因 Python 比较运算符（`<=`, `max()`）已兼容浮点运算 #### 示例分析： 输入：`[(4.2, 16.0), (14.47, 28.8)]` 1. 排序后：`[(4.2, 16.0), (14.47, 28.8)]`（起点已有序） 2. 检查第二区间：$14.47 ≤ 16.0$ → 合并为 `(4.2, max(16.0, 28.8)) = (4.2, 28.8)` 3. 输出：`[(4.2, 28.8)]` --- ### 关键点解析 1. **时间复杂度**：$O(n \log n)$ - 排序消耗 $O(n \log n)$ - 合并遍历消耗 $O(n)$ 2. **边界处理**： - 空输入直接返回空列表 - 单区间无需合并 - 完全覆盖区间（如 `[(1, 10), (2, 3)]`）可正确处理 3. **浮点精度**： 实际场景中若需高精度比较，可添加容差阈值： ```python tolerance = 1e-6 # 根据精度需求设定 if current_start <= last_end + tolerance: ... ``` ---