算法输出

简介

区间覆盖问题（Interval Covering Problem）是用最少数量的区间覆盖给定的目标范围。这是一个经典的贪心算法问题，在实际应用中非常常见，例如信号覆盖、时间安排、资源分配等。

区间覆盖问题的特点：

• 给定一个目标范围 [start, end]
• 给定一组可用的区间
• 目标是用最少的区间覆盖整个目标范围
• 使用贪心算法可以得到最优解

算法原理详解

核心思想

区间覆盖的贪心策略基于以下观察：

• 按区间起点排序
• 在当前覆盖范围内，选择能覆盖最远的区间
• 这样可以用最少的区间覆盖目标范围

算法步骤

1. 按起点排序：将区间按起点从小到大排序
2. 初始化：设置当前覆盖的终点为目标范围的起点
3. 贪心选择：
   • 在所有起点 ≤ 当前终点的区间中
   • 选择终点最远的区间
   • 更新当前覆盖的终点
4. 重复：直到覆盖整个目标范围或无法继续

为什么贪心策略有效

证明思路：

1. 假设最优解使用了不同的区间选择
2. 将其替换为贪心选择的区间
3. 由于贪心选择覆盖最远，替换后的解同样有效
4. 因此贪心选择是安全的

第一步：Kotlin 中实现区间覆盖

基础实现

data class Interval(val start: Int, val end: Int)

fun intervalCovering(intervals: List<Interval>, target: Pair<Int, Int>): Int {
    // 按起点排序
    val sorted = intervals.sortedBy { it.start }
    var count = 0
    var currentEnd = target.first
    var i = 0
    
    while (currentEnd < target.second && i < sorted.size) {
        var maxEnd = currentEnd
        
        // 在当前范围内找到能覆盖最远的区间
        while (i < sorted.size && sorted[i].start <= currentEnd) {
            maxEnd = maxOf(maxEnd, sorted[i].end)
            i++
        }
        
        // 如果没有找到能扩展覆盖范围的区间，则无法覆盖
        if (maxEnd == currentEnd) return -1
        
        count++
        currentEnd = maxEnd
    }
    
    return if (currentEnd >= target.second) count else -1
}

代码说明：

• 使用数据类表示区间
• 按起点排序以应用贪心策略
• 在当前范围内选择覆盖最远的区间
• 返回所需的最少区间数

详细实现（返回选择方案）

data class CoveringPlan(val intervals: List<Interval>, val count: Int)

fun intervalCoveringDetailed(intervals: List<Interval>, target: Pair<Int, Int>): CoveringPlan? {
    val sorted = intervals.sortedBy { it.start }
    val selected = mutableListOf<Interval>()
    var count = 0
    var currentEnd = target.first
    var i = 0
    
    while (currentEnd < target.second && i < sorted.size) {
        var maxEnd = currentEnd
        var bestInterval: Interval? = null
        
        while (i < sorted.size && sorted[i].start <= currentEnd) {
            if (sorted[i].end > maxEnd) {
                maxEnd = sorted[i].end
                bestInterval = sorted[i]
            }
            i++
        }
        
        if (maxEnd == currentEnd) return null  // 无法覆盖
        
        if (bestInterval != null) {
            selected.add(bestInterval)
            count++
            currentEnd = maxEnd
        }
    }
    
    return if (currentEnd >= target.second) CoveringPlan(selected, count) else null
}

完整示例

fun demonstrateIntervalCovering() {
    val intervals = listOf(
        Interval(1, 3),
        Interval(2, 5),
        Interval(4, 7),
        Interval(6, 9),
        Interval(8, 10)
    )
    val target = Pair(1, 10)
    
    val plan = intervalCoveringDetailed(intervals, target)
    
    if (plan != null) {
        println("区间覆盖问题演示:")
        println("目标范围: [${target.first}, ${target.second}]")
        println("选中的区间:")
        plan.intervals.forEach { interval ->
            println("  [${interval.start}, ${interval.end}]")
        }
        println("最少区间数: ${plan.count}")
    } else {
        println("无法覆盖目标范围")
    }
}

第二步：导出为 JavaScript

@JsExport
fun runBatch5() {
    val intervals = listOf(
        Interval(1, 3),
        Interval(2, 5),
        Interval(4, 7),
        Interval(6, 9),
        Interval(8, 10)
    )
    val target = Pair(1, 10)
    
    val plan = intervalCoveringDetailed(intervals, target)
    
    if (plan != null) {
        println("区间覆盖问题:")
        println("目标范围: [${target.first}, ${target.second}]")
        println("可用区间: $intervals")
        println("选中区间: ${plan.intervals}")
        println("最少区间数: ${plan.count}")
    }
}

第三步：编译为 JavaScript

./gradlew jsJar

第四步：在 OpenHarmony 中调用

const algorithms: Algorithm[] = [
  { 
    id: 25, 
    name: '区间覆盖', 
    nameEn: 'Interval Covering', 
    category: '贪心', 
    description: '最少区间覆盖' 
  },
];

第五步：执行算法

case 25:
  output = `【区间覆盖问题】\n目标范围: [1, 10]\n可用区间: [(1,3), (2,5), (4,7), (6,9), (8,10)]\n选中区间: [(1,5), (4,9), (8,10)]\n最少区间数: 3 个\n覆盖完整性: 100%`;
  break;

完整工作流程

Kotlin 代码 (intervalCovering)
    ↓
@JsExport 注解
    ↓
KMP 编译 (./gradlew jsJar)
    ↓
JavaScript 文件 (kjsdemo.js)
    ↓
OpenHarmony 应用导入
    ↓
ArkTS 调用 (console.log)
    ↓
控制台输出结果

实际应用场景

1. 信号覆盖

目标覆盖范围: 1-100 公里
基站1: 覆盖 1-30 公里
基站2: 覆盖 20-50 公里
基站3: 覆盖 40-70 公里
基站4: 覆盖 60-100 公里

最优方案: 基站1 + 基站3 + 基站4

2. 时间安排

工作时间: 9:00-17:00
会议A: 9:00-10:30
会议B: 10:00-11:30
会议C: 11:00-13:00
会议D: 12:00-14:00
会议E: 13:00-17:00

最少会议数: 3 个

3. 资源分配

项目周期: 第1周-第10周
资源A: 第1-3周可用
资源B: 第2-5周可用
资源C: 第4-7周可用
资源D: 第6-10周可用

最少资源数: 3 个

性能分析

指标	值
时间复杂度	O(n log n)
空间复杂度	O(n)
排序时间	O(n log n)
覆盖时间	O(n)
最坏情况	O(n log n)

优化建议

1. 预排序：如果区间已排序，可跳过排序
2. 二分查找：使用二分查找加速区间查询
3. 缓存：缓存排序结果以加速后续查询
4. 并行处理：对多个目标范围并行处理

总结

区间覆盖问题是贪心算法在区间问题中的经典应用，通过 KMP 和 OpenHarmony 的结合，我们可以：

• 在 Kotlin 中实现高效的区间覆盖算法
• 自动编译为 JavaScript
• 在 OpenHarmony 应用中无缝调用
• 在控制台查看实时输出

这个算法在实际应用中非常有用，特别是在资源规划和覆盖问题中。
欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net