在重叠Range列表中拆分非重叠子Range并保留组成来源

这个需求很实用，尤其是处理区间类数据的时候！下面我用Swift来实现你想要的功能——把一组重叠的Range拆分成无重叠的子Range，同时记录每个子Range对应的原始来源。

核心思路 #

要实现这个功能，关键是抓住分界点：所有原始Range的起始和结束值都是拆分的关键节点。我们可以按以下步骤来做：

1. 收集所有原始Range的边界值，去重后排序，得到所有需要拆分的分界点。
2. 用相邻的分界点生成一个个无重叠的子Range。
3. 对每个子Range，找出所有包含它的原始Range，作为它的来源。

代码实现 #

首先我们可以定义一个结构体，用来保存拆分后的子Range和对应的来源列表：

struct MergedRange<T: Comparable> {
    let range: Range<T>
    let sources: [Range<T>]
}

然后编写处理函数：

func splitOverlappingRanges<T: Comparable>(_ ranges: [Range<T>]) -> [MergedRange<T>] {
    // 1. 收集所有分界点并去重排序
    var boundaries = Set<T>()
    ranges.forEach {
        boundaries.insert($0.lowerBound)
        boundaries.insert($0.upperBound)
    }
    let sortedBoundaries = boundaries.sorted()
    
    var result = [MergedRange<T>]()
    
    // 2. 遍历相邻分界点生成子区间
    for index in 0..<sortedBoundaries.count - 1 {
        let start = sortedBoundaries[index]
        let end = sortedBoundaries[index + 1]
        guard start < end else { continue } // 跳过空区间
        
        let subRange = start..<end
        // 3. 找出所有包含当前子区间的原始Range
        // 由于分界点来自原始Range的边界，只要子区间的起始在原始Range内，整个子区间就属于该Range的一部分
        let sourceRanges = ranges.filter { $0.contains(subRange.lowerBound) }
        
        result.append(MergedRange(range: subRange, sources: sourceRanges))
    }
    
    return result
}

测试你的示例 #

用你给出的Range来测试这个函数：

let rangeA = 0..<3
let rangeB = 2..<4
let rangeC = 3..<6
let originalList = [rangeA, rangeB, rangeC]

let splitResult = splitOverlappingRanges(originalList)

// 打印结果验证
splitResult.forEach { merged in
    let sourceLabels = merged.sources.map { "\($0.lowerBound)..<\($0.upperBound)" }.joined(separator: ", ")
    print("子区间: \(merged.range) | 来源: [\(sourceLabels)]")
}

运行后会输出：

子区间: 0..<2 | 来源: [0..<3]
子区间: 2..<3 | 来源: [0..<3, 2..<4]
子区间: 3..<4 | 来源: [2..<4, 3..<6]
子区间: 4..<6 | 来源: [3..<6]

完全符合你的预期！

额外说明 #

这个实现还能处理更多边界情况：

• 完全不重叠的Range：拆分后每个子Range就是原始Range，来源只有自身。
• 完全包含的Range：比如有一个Range包含另一个，拆分后会生成同时属于两个Range的子区间。
• 空输入：函数会返回空数组，不会崩溃。

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