时间戳

首页 > 解决方案 > 任务调度算法

algorithm - 任务调度算法

问题描述

我该如何解决以下问题？我有使用DP的感觉

给定任务复杂度的数组，注意复杂度也是它们需要执行的任务的顺序。约束是每天至少安排一项任务。当天的复杂度是当天最高的任务复杂度。通过优化规划可以实现的总体最小复杂度是多少？

例如，假设有n = 5任务，其中：

complexity = [1, 5, 3, 2, 4]

并且测试的长度是days = 2。最好的选择是在第一天执行第一个任务，在第二天执行其余任务。第一天的复杂度是 1，因为这是唯一的任务，第二天的复杂度是 5，因为这是当天最复杂任务的复杂度级别。因此，答案是1 + 5 = 6。

Example 1:
5 -> complexity[] size n = 5
30
10
40
20
50
2 -> Days =2

输出：

80

标签： algorithmscheduled-tasksdynamic-programming

解决方案

我认为这是 O(n 2 )，所以不是超级最优，但它有效。它是用 Go 编写的。

package main

import "fmt"

func optimize(tasks []int, days int) int {
    // edge case 1: empty c or days <= 0
    // (this is really for data input validation)
    if len(tasks) == 0 || days <= 0 {
        return 0
    }
    // edge case 2: single day - return max
    if days == 1 {
        max := tasks[0]
        for _, v := range tasks[1:] {
            if v > max {
                max = v
            }
        }
        return max
    }
    // edge case 3: tasks = days
    if days == len(tasks) {
        total := 0
        for _, v := range tasks {
            total += v
        }
        return total
    }
    // all other cases:
    possibilities := []int{}
    i := 0
    max := tasks[0]
    for {
        tasksLeft := len(tasks[i+1:])
        daysLeft := days - 1
        if tasksLeft < daysLeft {
            break
        }
        if tasks[i] > max {
            max = tasks[i]
        }
        possibility := max + optimize(tasks[i+1:], days-1)
        possibilities = append(possibilities, possibility)
        i++
    }
    // minimize
    min := possibilities[0]
    for _, p := range possibilities[1:] {
        if p < min {
            min = p
        }
    }
    return min
}

func main() {
    tasks := []int{1, 5, 3, 2, 4}
    days := 2
    fmt.Println(optimize(tasks, days))
}

推荐阅读