摘要

区间合并算法是计算机科学中的经典问题，广泛应用于日程安排、资源调度、时间窗口管理等场景。本文将深入探讨区间合并与重叠检测的核心算法原理，详细解析 Kotlin/JS 实现的代码细节，并从工程化角度分析算法的优化策略和实际应用。

1. 算法背景与问题定义

1.1 问题描述

给定一组区间，每个区间由起始点和结束点表示，要求合并所有重叠的区间。两个区间 [a, b] 和 [c, d] 重叠的条件是：

a <= d && b >= c

或者更直观地表示为：

interval1.end >= interval2.start && interval1.start <= interval2.end

1.2 应用场景

• 日程管理系统：合并用户的时间段，避免重复预约
• 资源调度：合并服务器占用时间段，优化资源分配
• 网络路由：合并 IP 地址段，减少路由表大小
• 数据库优化：合并查询时间范围，减少数据库访问次数

2. 核心算法原理

2.1 排序合并法（推荐算法）

核心思想：将区间按起始点排序，然后遍历合并重叠区间。

算法步骤：

1. 排序阶段：对所有区间按起始点升序排序
2. 合并阶段：维护当前合并区间，遍历后续区间：
   • 如果新区间的起始点 <= 当前区间的结束点，说明重叠，更新当前区间的结束点
   • 否则，保存当前区间，开始新的合并区间

时间复杂度分析：

• 排序：O(n log n)
• 线性扫描：O(n)
• 总体：O(n log n)

空间复杂度：O(n)，用于存储结果

2.2 暴力法

核心思想：对每个区间，检查是否与其他区间重叠，如果重叠则合并。

算法步骤：

1. 遍历每个区间
2. 对当前区间，检查所有其他区间是否有重叠
3. 如果重叠，合并区间并标记已使用
4. 重复直到所有区间都处理完成

时间复杂度：O(n²)，最坏情况下每个区间都要与其他所有区间比较

空间复杂度：O(n)

3. 代码实现深度解析

3.1 输入解析模块

var intervals: List<Pair<Int, Int>>? = null

payload.lines()
    .map { it.trim() }
    .filter { it.isNotEmpty() }
    .forEach { line ->
        when {
            line.startsWith("intervals=", ignoreCase = true) -> {
                val valuesStr = line.substringAfter("=").trim()
                try {
                    val nums = valuesStr.split(",")
                        .map { it.trim() }
                        .filter { it.isNotEmpty() }
                        .map { it.toInt() }
                    
                    if (nums.size % 2 != 0) {
                        intervals = null
                    } else {
                        intervals = (0 until nums.size step 2).map {
                            Pair(nums[it], nums[it + 1])
                        }
                    }
                } catch (e: Exception) {
                    intervals = null
                }
            }
            // ... 其他解析逻辑
        }
    }

代码解析：

这段代码实现了灵活的输入解析机制。首先，它支持两种输入格式：

• 明确格式：intervals=1,3,2,6,8,10
• 隐式格式：直接输入逗号分隔的数字

解析过程采用函数式编程风格，通过 lines() 将输入按行分割，然后使用链式操作进行过滤和转换。关键点在于处理数字对的配对逻辑：

• 使用 step 2 遍历，每次取两个数字组成一个区间对
• 通过 nums.size % 2 != 0 检查确保数字数量为偶数
• 使用 Pair(nums[it], nums[it + 1]) 创建区间对，其中第一个数字为起始点，第二个为结束点

错误处理采用 try-catch 机制，确保解析失败时不会崩溃，而是返回 null 并在后续进行统一处理。

3.2 区间有效性验证

val validIntervals = intervalList.filter { it.first <= it.second }
if (validIntervals.size != intervalList.size) {
    builder.appendLine("⚠️ 警告: 发现无效区间（起始值 > 结束值），已自动过滤")
    builder.appendLine("有效区间: ${validIntervals.joinToString(", ") { "[${it.first}, ${it.second}]" }}")
    builder.appendLine()
}

代码解析：

区间有效性验证是算法的关键预处理步骤。这里使用了 Kotlin 的高阶函数 filter 来过滤无效区间。条件 it.first <= it.second 确保每个区间的起始点不大于结束点，这是区间的基本语义要求。

这种设计体现了防御性编程的思想：

• 自动修复用户输入错误，而不是直接拒绝
• 提供清晰的警告信息，告知用户哪些区间被过滤
• 使用友好的输出格式，提高用户体验

3.3 排序合并法核心实现

fun mergeIntervalsSort(intervals: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    if (intervals.isEmpty()) return emptyList()

    val sorted = intervals.sortedBy { it.first }
    val result = mutableListOf<Pair<Int, Int>>()
    var current = sorted[0]

    for (i in 1 until sorted.size) {
        val next = sorted[i]
        if (current.second >= next.first) {
            // 重叠，合并
            current = Pair(current.first, maxOf(current.second, next.second))
        } else {
            // 不重叠，保存当前区间，开始新的区间
            result.add(current)
            current = next
        }
    }
    result.add(current)

    return result
}

代码解析：

这是算法的核心实现部分，体现了贪心算法的思想。

边界处理：

• 首先检查空列表，直接返回空结果，避免后续处理错误

排序策略：

• 使用 sortedBy { it.first } 按起始点排序，这是合并算法的关键前提
• Kotlin 的排序是稳定的，保证相同起始点的区间相对顺序不变

合并逻辑详解：

• var current = sorted[0]：初始化当前合并区间为第一个区间
• 重叠判断条件 current.second >= next.first：
  • 如果当前区间的结束点 >= 下一个区间的起始点，说明有重叠
  • 这里使用 >= 而不是 >，包含了相邻区间（相接）的情况，通常也视为需要合并
• 合并操作 Pair(current.first, maxOf(current.second, next.second))：
  • 保持起始点不变（因为已经排序，当前起始点是最小的）
  • 结束点取两个区间的最大值，实现区间扩展
• 非重叠处理：将当前区间加入结果列表，然后开始新的合并区间

循环后的处理：

• 循环结束后，current 保存的是最后一个合并区间（或未合并的最后一个区间）
• 需要显式添加到结果中，这是算法实现的常见陷阱

3.4 暴力法实现细节

fun mergeIntervalsBruteForce(intervals: List<Pair<Int, Int>>): List<Pair<Int, Int>> {
    if (intervals.isEmpty()) return emptyList()

    val merged = mutableListOf<Pair<Int, Int>>()
    val used = BooleanArray(intervals.size)

    for (i in intervals.indices) {
        if (used[i]) continue

        var current = intervals[i]
        var changed = true

        while (changed) {
            changed = false
            for (j in intervals.indices) {
                if (i != j && !used[j]) {
                    val other = intervals[j]
                    if (current.first <= other.second && current.second >= other.first) {
                        // 重叠，合并
                        current = Pair(
                            minOf(current.first, other.first),
                            maxOf(current.second, other.second)
                        )
                        used[j] = true
                        changed = true
                    }
                }
            }
        }

        merged.add(current)
        used[i] = true
    }

    return merged.sortedBy { it.first }
}

代码解析：

暴力法实现虽然效率较低，但思路直观，在某些特殊场景下可能更容易理解。

标记数组设计：

• 使用 BooleanArray 标记已处理的区间，避免重复处理
• 初始化为 false，表示所有区间都未使用

双重循环结构：

• 外层循环：遍历每个区间作为起始点
• 内层 while 循环：持续合并，直到无法再合并为止
  • changed 标志位控制循环，只有发生合并时才继续
  • 这种设计可以处理多个区间连续重叠的情况

重叠判断条件：

current.first <= other.second && current.second >= other.first

这是标准的区间重叠判断公式，比排序法的判断更全面，因为暴力法不要求排序。

合并策略：

• 起始点取最小值：minOf(current.first, other.first)
• 结束点取最大值：maxOf(current.second, other.second)
• 这样确保合并后的区间覆盖所有重叠区间

性能优化点：

• 使用 used 数组避免重复处理，但时间复杂度仍然是 O(n²)
• 最后对结果排序，保证输出有序

3.5 合并过程可视化

if (validIntervals.size <= 15) {
    builder.appendLine("🔬 合并过程分析（排序法）")
    val sorted = validIntervals.sortedBy { it.first }
    
    builder.appendLine("步骤1: 按起始值排序")
    builder.appendLine("排序后: ${sorted.joinToString(", ") { "[${it.first}, ${it.second}]" }}")
    builder.appendLine()
    
    // ... 详细的步骤输出
}

代码解析：

这部分代码实现了算法的过程可视化，对于理解和调试算法非常有价值。

条件限制：

• 只在区间数量 <= 15 时显示详细过程，避免输出过长
• 这是工程实践中常见的优化策略：在详细性和可读性之间平衡

步骤分解输出：

• 显示排序结果，让用户理解算法的第一步
• 逐个区间显示合并决策过程
• 明确标注重叠判断和合并操作

这种设计体现了算法可视化的重要性，特别是在教学和调试场景中。

3.6 区间可视化实现

if (validIntervals.size <= 12) {
    builder.appendLine("📈 区间可视化")
    val allNumbers = (validIntervals.flatMap { listOf(it.first, it.second) } 
                      + result1.flatMap { listOf(it.first, it.second) })
                      .distinct().sorted()
    val minVal = allNumbers.firstOrNull() ?: 0
    val maxVal = allNumbers.lastOrNull() ?: 0
    val range = maxVal - minVal

    if (range <= 50) {
        // 绘制区间线条
        validIntervals.forEach { interval ->
            val start = interval.first - minVal
            val end = interval.second - minVal
            val line = StringBuilder()
            for (i in 0..range) {
                if (i >= start && i <= end) {
                    line.append("━")
                } else {
                    line.append(" ")
                }
            }
            builder.appendLine("  [${interval.first}, ${interval.second}]: $line")
        }
    }
}

代码解析：

这段代码实现了文本形式的区间可视化，是算法输出的亮点之一。

数值范围计算：

• 使用 flatMap 展开所有区间的起始和结束点
• distinct().sorted() 获取所有唯一值并排序
• 计算最小值和最大值，确定可视化范围

归一化处理：

• interval.first - minVal：将区间坐标归一化到 [0, range] 范围
• 这样可以处理任意大小的区间值，统一显示格式

字符绘制：

• 使用 ━（Unicode 字符）表示区间范围
• 使用空格表示区间外区域
• 这种文本可视化虽然简单，但直观易懂

性能考虑：

• 限制范围 <= 50，避免生成过长的字符串
• 只在区间数量 <= 12 时显示，保持输出简洁

4. 算法复杂度与性能分析

4.1 时间复杂度对比

方法	最佳情况	平均情况	最坏情况	说明
排序合并法	O(n log n)	O(n log n)	O(n log n)	排序占主导
暴力法	O(n²)	O(n²)	O(n²)	双重循环

4.2 空间复杂度分析

• 排序合并法：O(n)

  • 排序需要 O(n) 额外空间（原地排序可优化为 O(1)）
  • 结果存储需要 O(n) 空间
  • 总体：O(n)

• 暴力法：O(n)

  • used 数组：O(n)
  • 结果存储：O(n)
  • 总体：O(n)

4.3 实际性能考虑

1. 小规模数据（n < 100）：

   • 两种方法性能差异不明显
   • 可以考虑使用暴力法，代码更简单

2. 中等规模数据（100 ≤ n < 10,000）：

   • 排序合并法明显优于暴力法
   • 推荐使用排序合并法

3. 大规模数据（n ≥ 10,000）：

   • 排序合并法是唯一选择
   • 可以考虑并行排序优化

5. 算法优化与扩展

5.1 原地排序优化

// 如果输入是可变的，可以使用原地排序
intervals.sortBy { it.first }
// 空间复杂度降低到 O(1)

5.2 并行化处理

对于超大规模数据，可以考虑：

• 并行排序（Parallel Sort）
• 分段合并后合并结果
• 使用 MapReduce 框架

5.3 变体问题扩展

1. 插入新区间：在已合并的区间列表中插入新区间并合并
2. 删除区间：从区间列表中删除指定区间
3. 查询重叠：快速查找与给定区间重叠的所有区间
4. 区间计数：统计某个点被多少个区间覆盖

6. 工程化实践要点

6.1 错误处理

代码中实现了多层次的错误处理：

• 输入验证：检查格式、数值有效性
• 区间验证：过滤无效区间（起始 > 结束）
• 异常捕获：使用 try-catch 防止程序崩溃

6.2 用户体验优化

• 清晰的输出格式：使用分隔线和图标
• 过程可视化：显示合并过程的每一步
• 友好的错误提示：明确指出问题所在
• 性能统计：显示减少了多少个区间

6.3 代码可维护性

• 函数拆分：将不同方法封装为独立函数
• 命名清晰：使用描述性的变量和函数名
• 注释完善：关键逻辑都有注释说明

7. 实际应用案例

7.1 日程管理系统

// 用户输入多个时间段
val meetings = listOf(
    Pair(9, 10),   // 9:00-10:00
    Pair(9, 30, 10, 30),  // 9:30-10:30
    Pair(14, 15)   // 14:00-15:00
)

// 合并重叠时间段，得到实际占用时间
val merged = mergeIntervalsSort(meetings)
// 结果: [(9, 10, 30), (14, 15)]

7.2 资源调度优化

在云服务器资源调度中，需要合并多个任务的时间占用区间，优化资源分配。

7.3 数据库查询优化

将多个时间范围查询合并为更少的查询，减少数据库访问次数。

8. 总结

区间合并算法虽然看似简单，但在实际工程应用中却非常重要。本文详细解析了两种主要实现方法的代码细节，从输入解析到结果输出，从算法原理到工程实践，全面展示了如何实现一个高质量、易维护的区间合并工具。

核心要点：

1. 排序合并法是最优解，时间复杂度 O(n log n)
2. 暴力法虽然效率低，但思路直观，适合小规模数据
3. 工程化实现需要考虑错误处理、用户体验和可维护性
4. 可视化输出有助于理解和调试算法

未来优化方向：

• 支持更复杂的数据类型（日期时间、浮点数等）
• 实现增量更新（插入/删除区间）
• 添加区间查询功能
• 优化大规模数据的处理性能

通过深入理解算法原理和代码实现，我们可以更好地将区间合并算法应用到实际项目中，解决各种区间相关的实际问题。

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net