2022-04-26：给定一个数组 componets，长度为 A， componets[i] = j，代表 i 类型的任务需要耗时 j 给定一个二维数组 orders，长度为 M， orders[i][0] 代表 i

2023-04-26
北京
本文字数：3877 字
阅读完需：约 13 分钟

2022-04-26：给定一个数组 componets，长度为 A，componets[i] = j，代表 i 类型的任务需要耗时 j 给定一个二维数组 orders，长度为 M，orders[i][0]代表 i 号订单下单时间 orders[i][1]代表 i 号订单是哪种类型的任务，毫无疑问 orders[i][1] < A 一开始所有流水线都在 0 时刻待命，给定一个正数 nums，表示流水线的数量，流水线编号为 0 ~ nums-1 每一个流水线可以承接任何类型的任务，耗时就是 componets 数组给定的所有订单的下单时间一定是有序的，也就是 orders 数组，是根据下单时间排序的每一个订单开始执行的时间不能早于下单时间，如果有多个流水线都可以执行当前订单，选择编号最小的流水线根据上面说的任务执行细节，去依次完成所有订单返回长度为 M 的数组 ans，也就是和 orders 等长 ans[i][0]代表 i 号订单是由哪条流水线执行的 ans[i][1]代表 i 号订单的完成时间 1 <= A <= 10^51 <= M <= 10^51 <= nums <= 10^51 <= 时间数值 <= 10^5。

答案 2022-04-26：

第一种算法大体过程：

初始化一个长度为 nums 的流水线数组 lines，初始值都为 0。
遍历订单数组 orders 中的每个订单 i，获取订单的下单时间 startTime 和任务类型 typ。
在流水线数组 lines 中查找第一个可用的流水线 usei，使得 lines[usei] <= startTime。如果找到了可用的流水线，将此订单分配给该流水线；否则，寻找结束时间最早的流水线 early，并将此订单分配给 early 流水线。
更新流水线数组 lines 中对应流水线的状态，即 lines[usei] = ans[i][1]，其中 ans[i][1] 是该订单完成的时间。
将当前订单的结果保存到输出数组 ans 中，即 ans[i][0] = usei，ans[i][1] = lines[usei]。
返回 ans 数组。

时间复杂度为 O(nums * M)，其中 nums 是流水线数量，M 是订单数量。空间复杂度为 O(M)。

第二种算法大体过程：

初始化一个长度为 nums 的可用流水线堆 canUseLines，以及一个睡眠流水线堆 sleepLines。
遍历订单数组 orders 中的每个订单 i，获取订单的下单时间 startTime 和任务类型 jobType。
从睡眠流水线堆 sleepLines 中弹出所有满足条件的流水线，并将这些流水线加入可用流水线堆 canUseLines 中。
从可用流水线堆 canUseLines 中选择编号最小的流水线 use，并将此订单分配给该流水线。
更新流水线的状态，即将 use 流水线从可用流水线堆 canUseLines 中弹出，更新其结束时间为此订单完成时间 ans[i][1]，然后将其加入到睡眠流水线堆 sleepLines 中。
将当前订单的结果保存到输出数组 ans 中，即 ans[i][0] = use.index，ans[i][1] = use.time。
返回 ans 数组。

时间复杂度为 O(M * log(nums))，其中 M 是订单数量，nums 是流水线数量。由于使用了堆来维护可用流水线和睡眠流水线，每次操作的时间复杂度是 log(nums)，因此总时间复杂度为 M * log(nums)。空间复杂度为 O(nums + M)，即可用流水线堆和睡眠流水线堆的大小之和，加上输出数组 ans 的大小。

go 完整代码如下：

package main
import (  "container/heap"  "fmt"  "math"  "math/rand"  "sort"  "time")
func Times1(nums int, jobTimes []int, orders [][]int) [][]int {  lines := make([]int, nums)  n := len(orders)  ans := make([][]int, n)  for i := 0; i < n; i++ {    ans[i] = make([]int, 2)  }  for i := 0; i < n; i++ {    start, typ := orders[i][0], orders[i][1]    usei := -1    for j := 0; j < nums; j++ {      if lines[j] <= start {        usei = j        break      }    }    if usei != -1 {      ans[i][0] = usei      ans[i][1] = start + jobTimes[typ]    } else {      early := math.MaxInt32      for j := 0; j < nums; j++ {        if lines[j] < early {          early = lines[j]          usei = j        }      }      ans[i][0] = usei      ans[i][1] = early + jobTimes[typ]    }    lines[usei] = ans[i][1]  }  return ans}
type Line struct {  time  int  index int}
type WakeUpHeap []*Line
func (h WakeUpHeap) Len() int { return len(h) }func (h WakeUpHeap) Less(i, j int) bool {  if h[i].time != h[j].time {    return h[i].time < h[j].time  }  return h[i].index < h[j].index}func (h WakeUpHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *WakeUpHeap) Push(x interface{}) {  *h = append(*h, x.(*Line))}func (h *WakeUpHeap) Pop() interface{} {  old := *h  n := len(old)  x := old[n-1]  *h = old[:n-1]  return x}
type IndexHeap []*Line
func (h IndexHeap) Len() int           { return len(h) }func (h IndexHeap) Less(i, j int) bool { return h[i].index < h[j].index }func (h IndexHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }func (h *IndexHeap) Push(x interface{}) {  *h = append(*h, x.(*Line))}func (h *IndexHeap) Pop() interface{} {  old := *h  n := len(old)  x := old[n-1]  *h = old[:n-1]  return x}
func Times2(nums int, componets []int, orders [][]int) [][]int {  n := len(orders)  // 睡眠堆  sleepLines := make(WakeUpHeap, 0)  heap.Init(&sleepLines)  // 可用堆  canUseLines := make(IndexHeap, nums)  for i := 0; i < nums; i++ {    canUseLines[i] = &Line{0, i}  }  heap.Init(&canUseLines)  ans := make([][]int, n)  for i := 0; i < n; i++ {    ans[i] = make([]int, 2)  }  for i := 0; i < n; i++ {    startTime, jobType := orders[i][0], orders[i][1]    // 当前订单在start时刻下单，所有唤醒时间比time早的流水线全可以考虑    for len(sleepLines) > 0 && sleepLines[0].time <= startTime {      heap.Push(&canUseLines, heap.Pop(&sleepLines))    }    // 如果可以使用的流水线不存在    // 比如，2条流水线    // 第0个订单，1时刻开始，用时100万，流水线A在100万+1时刻醒来    // 第1个订单，2时刻开始，用时100万，流水线B在100万+2时刻醒来    // 轮到第3个订单，3时刻开始，用时100万    // 会发现可用流水线已经没有了，此时需要等到流水线A在100万+1时刻醒来，做当前订单    var use *Line    if len(canUseLines) == 0 {      // 如果当前时刻，可以使用的流水线不存在，需要等到可以唤醒的最早那个      // 如果可以唤醒的最早流水线，不只一个      // 选编号小的，看比较器的注释      use = heap.Pop(&sleepLines).(*Line)      ans[i][1] = use.time + componets[jobType]    } else {      // 如果当前时刻，可以使用的流水线存在，需要使用编号最小的      use = heap.Pop(&canUseLines).(*Line)      ans[i][1] = startTime + componets[jobType]    }    ans[i][0] = use.index    use.time = ans[i][1]    heap.Push(&sleepLines, use)  }  return ans}
func randomArray(n, v int) []int {  ans := make([]int, n)  rand.Seed(time.Now().UnixNano())  for i := 0; i < n; i++ {    ans[i] = rand.Intn(v) + 1  }  return ans}
func randomMatrix(n, a, b int) [][]int {  ans := make([][]int, n)  rand.Seed(time.Now().UnixNano())  for i := 0; i < n; i++ {    ans[i] = []int{rand.Intn(a) + 1, rand.Intn(b)}  }  return ans}
func main() {  N := 100  M := 300  V := 10000  testTimes := 5000  fmt.Println("功能测试开始")  for i := 0; i < testTimes; i++ {    nums := rand.Intn(N) + 1    orderNumber := rand.Intn(M) + 1    types := rand.Intn(N) + 1    componets := randomArray(types, V)    orders := randomMatrix(orderNumber, V, types)    sort.Slice(orders, func(i, j int) bool { return orders[i][0] < orders[j][0] })    ans1 := Times1(nums, componets, orders)    ans2 := Times2(nums, componets, orders)    for j := range ans1 {      if ans1[j][0] != ans2[j][0] || ans1[j][1] != ans2[j][1] {        fmt.Println("出错了！")        fmt.Println(nums)        for _, num := range componets {          fmt.Printf("%d ", num)        }        fmt.Println()        for _, order := range orders {          fmt.Printf("(%d, %d) ", order[0], order[1])        }        fmt.Println()        fmt.Print("ans1 : ")        for _, cur := range ans1 {          fmt.Printf("(%d, %d) ", cur[0], cur[1])        }        fmt.Println()        fmt.Print("ans2 : ")        for _, cur := range ans2 {          fmt.Printf("(%d, %d) ", cur[0], cur[1])        }        fmt.Println()        return      }    }  }  fmt.Println("功能测试结束")
  fmt.Println("性能测试开始")  N = 100000  M = 500000  V = 100000  nums := N  componets := randomArray(N, V)  orders := randomMatrix(M, V, N)  sort.Slice(orders, func(i, j int) bool { return orders[i][0] < orders[j][0] })  fmt.Println("流水线数量 : ", N)  fmt.Println("订单数量 : ", M)  fmt.Println("时间数值范围 : ", V)  start := time.Now()  Times2(nums, componets, orders)  end := time.Now()  fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")  fmt.Println("性能测试结束")}