算法输出

简介

任务调度问题（Job Sequencing with Deadlines）是在给定截止时间和利润的情况下，选择最大利润的任务子集。这是一个经典的贪心算法问题，广泛应用于生产调度、项目管理等领域。

任务调度问题的特点：

• 每个任务有一个截止时间和利润
• 每个任务只能执行一次
• 每个任务执行时间为 1 个单位
• 目标是最大化总利润

算法原理详解

核心思想

任务调度的贪心策略基于以下观察：

• 按利润从高到低排序任务
• 对每个任务，在其截止时间内找到最晚的可用时间槽
• 如果找到可用槽，则分配该任务
• 这样可以为其他任务留出更多的时间

算法步骤

1. 按利润排序：将任务按利润从高到低排序
2. 初始化时间槽：创建时间槽数组，初始状态都未被占用
3. 分配任务：
   • 对每个任务，从其截止时间向前查找
   • 找到第一个未被占用的时间槽
   • 将任务分配到该时间槽
4. 计算总利润：累加所有被分配任务的利润

为什么贪心策略有效

证明思路：

1. 假设最优解中包含利润较低的任务
2. 将其替换为利润较高的任务
3. 由于利润更高，替换后的解更优
4. 因此贪心选择是安全的

第一步：Kotlin 中实现任务调度

基础实现

data class Job(val id: Int, val profit: Int, val deadline: Int)

fun jobScheduling(jobs: List<Job>): Int {
    // 按利润从高到低排序
    val sorted = jobs.sortedByDescending { it.profit }
    val maxDeadline = jobs.maxOf { it.deadline }
    val slot = BooleanArray(maxDeadline + 1)
    var totalProfit = 0
    
    // 为每个任务分配时间槽
    for (job in sorted) {
        // 从截止时间向前查找可用槽
        for (j in minOf(job.deadline, maxDeadline) downTo 1) {
            if (!slot[j]) {
                slot[j] = true
                totalProfit += job.profit
                break
            }
        }
    }
    
    return totalProfit
}

代码说明：

• 使用数据类表示任务
• 按利润排序以应用贪心策略
• 时间槽数组记录每个时间是否被占用
• 从截止时间向前查找可用槽

详细实现（返回调度方案）

data class Schedule(val jobId: Int, val assignedTime: Int, val profit: Int)

fun jobSchedulingDetailed(jobs: List<Job>): Pair<List<Schedule>, Int> {
    val sorted = jobs.sortedByDescending { it.profit }
    val maxDeadline = jobs.maxOf { it.deadline }
    val slot = IntArray(maxDeadline + 1) { -1 }  // -1 表示未被占用
    val schedules = mutableListOf<Schedule>()
    var totalProfit = 0
    
    for (job in sorted) {
        for (j in minOf(job.deadline, maxDeadline) downTo 1) {
            if (slot[j] == -1) {
                slot[j] = job.id
                schedules.add(Schedule(job.id, j, job.profit))
                totalProfit += job.profit
                break
            }
        }
    }
    
    return Pair(schedules, totalProfit)
}

完整示例

fun demonstrateJobScheduling() {
    val jobs = listOf(
        Job(1, 100, 2),
        Job(2, 80, 1),
        Job(3, 60, 3),
        Job(4, 70, 2)
    )
    
    val (schedules, totalProfit) = jobSchedulingDetailed(jobs)
    
    println("任务调度问题演示:")
    println("任务列表:")
    jobs.forEach { job ->
        println("  任务${job.id}: 利润${job.profit}, 截止时间${job.deadline}")
    }
    println("\n调度方案:")
    schedules.forEach { (jobId, time, profit) ->
        println("  时间槽$time: 任务$jobId (利润$profit)")
    }
    println("总利润: $totalProfit")
}

第二步：导出为 JavaScript

@JsExport
fun runBatch5() {
    val jobs = listOf(
        Job(1, 100, 2),
        Job(2, 80, 1),
        Job(3, 60, 3),
        Job(4, 70, 2)
    )
    
    val (schedules, totalProfit) = jobSchedulingDetailed(jobs)
    
    println("任务调度问题:")
    println("任务信息:")
    jobs.forEach { job ->
        println("  任务${job.id}: 利润${job.profit}, 截止${job.deadline}")
    }
    println("调度结果: $schedules")
    println("最大利润: $totalProfit")
}

第三步：编译为 JavaScript

./gradlew jsJar

第四步：在 OpenHarmony 中调用

const algorithms: Algorithm[] = [
  { 
    id: 24, 
    name: '任务调度', 
    nameEn: 'Job Scheduling', 
    category: '贪心', 
    description: '最大利润调度' 
  },
];

第五步：执行算法

case 24:
  output = `【任务调度问题】\n任务: [(100,2), (80,1), (60,3), (70,2)]\n按利润排序: 4个任务\n时间槽: 3个\n选中任务: (100,2), (80,1), (60,3)\n最大利润: 240\n利用率: 100%`;
  break;

完整工作流程

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

实际应用场景

1. 生产调度

工厂有 3 条生产线
任务A: 利润 100, 截止时间 2 天
任务B: 利润 80, 截止时间 1 天
任务C: 利润 60, 截止时间 3 天

最优调度:
- 第1天: 任务B
- 第2天: 任务A
- 第3天: 任务C
总利润: 240

2. 项目管理

可用时间: 5 个工作日
项目A: 收益 500, 需要 2 天
项目B: 收益 400, 需要 1 天
项目C: 收益 300, 需要 3 天

最优分配: 项目A + 项目B + 项目C

3. 会议安排

会议室可用: 5 个时间槽
会议A: 重要度 10, 需要 2 号前完成
会议B: 重要度 8, 需要 1 号前完成
会议C: 重要度 6, 需要 3 号前完成

性能分析

指标	值
时间复杂度	O(n²)
空间复杂度	O(n)
排序时间	O(n log n)
分配时间	O(n × maxDeadline)
最坏情况	O(n²)

优化建议

1. 使用并查集：可以优化时间槽查找到 O(n log n)
2. 优先队列：对于动态任务，使用优先队列
3. 预处理：缓存截止时间信息
4. 并行处理：对多个独立的调度问题并行处理

总结

任务调度问题是贪心算法在资源分配中的经典应用，通过 KMP 和 OpenHarmony 的结合，我们可以：

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

这个算法在实际生产和项目管理中非常有用。

---

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