任务最优调度

题目描述

给定一个正整数数组表示待系统执行的任务列表，数组的每一个元素代表一个任务，元素的值表示该任务的类型。

请计算执行完所有任务所需的最短时间。

任务执行规则如下

1. 任务可以按任意顺序执行，且每个任务执行耗时间均为1个时间单位
2. 两个同类型的任务之间必须有长度为N个单位的冷却时间，比如N为2时，在时间K执行了类型3的任务，那么K+1和K+2两个时间不能执行类型3任务
3. 系统在任何一个单位时间内都可以执行一个任务，或者等待状态。

说明:数组最大长度为1000，速度最大值1000。

输入描述

第一行记录一个用半角逗号分隔的数组，数组长度不超过1000，数组元素的值不超过1000。第二行记录任务冷却时间，N为正整数，N<=100.

输出描述

输出为执行完所有任务所需的最短时间。

用例

输入
2,2,2,3
2
输出
7
时间1: 执行类型2任务
时间2: 执行类型3任务(因为冷却时间为2，所以时间2不能执行类型2任务)
时间3: 系统等待(仍然在等待类型2的冷却时间)
时间4: 执行类型2任务
时间5: 等待
时间6: 等待
时间7: 执行类型2任务

解题思路

调度可以理解为：在一个时间单位内，选择一个个数大于0且未处于冷却的任务。将任务列表改造为任务id:[个数, 冷却时间]的形式。遍历列表，当一个任务个数大于0且冷却时间等于0则该任务可以被执行，此时任务数减一并重置冷却时间，其余任务则缩短冷却时间。不断重复这个流程直到所有任务都被完成，此时使用的时间就是最短时间

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func main() {
	in := bufio.NewScanner(os.Stdin)
	lines := make([]string, 0)
	for in.Scan() {
		lines = append(lines, in.Text())
	}
	wait, _ := strconv.Atoi(lines[1])
	m := make(map[string][]int)
	tmp := strings.Split(lines[0], ",")
	for _, v := range tmp {
		if _, ok := m[v]; !ok {
          	// 任务id:[个数,冷却时间]
			m[v] = []int{1, 0}
		} else {
			m[v][0]++
		}
	}
	n := len(tmp)
	ans := 0
	for n > 0 {
		ans++
		finish := false
		for _, v := range m {
			// 本轮时间执行了任务，其他任务等待
			if !finish && v[0] > 0 && v[1] == 0 {
				finish = true
				n--
				v[0]--
				v[1] = wait
			} else if v[1] > 0 {
				v[1]--
			}
		}
	}
	fmt.Println(ans)
}