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^5
1 <= M <= 10^5
1 <= nums <= 10^5
1 <= 时间数值 <= 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("性能测试结束")
}
