刷题笔记合集🔗

任务最优调度-200

问题描述

小柯有一个计算机系统，需要处理多个不同类型的任务。每个任务都有一个特定的类型标识，并且相同类型的任务之间需要有冷却时间。她需要找出执行完所有任务所需的最短时间。

任务执行规则如下：

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

输入格式

第一行记录一个用半角逗号分隔的数组，表示任务类型列表，数组长度不超过 ，数组元素的值不超过 。

第二行记录任务冷却时间 ， 为正整数，。

输出格式

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

样例输入

2,2,2,3
2

2,2,2,3,3,3
2

样例输出

7

10

数据范围

• 任务列表长度
• 任务类型标识
• 

题解

这道题目是关于任务调度和冷却时间的问题，看似复杂，实际上可以用贪心算法巧妙解决。

首先，我们需要理解一个关键点：完成所有任务的最短时间主要受数量最多的任务类型影响。因为这类任务之间必须要有冷却时间，这会"拉长"整个执行过程。

思路分析

假设我们有某种任务类型 A，它出现了 次（即任务数量最多的类型），冷却时间为 ：

1. 首先，这 个相同类型的任务至少需要占用 个时间单位
2. 在相邻两个 A 类型任务之间，必须间隔 个时间单位
3. 总共有 个间隔，每个间隔需要 个时间单位

所以，仅考虑最多数量的任务类型，最少需要的时间是：

但还有两种特殊情况需要考虑：

1. 如果有多个任务类型的数量并列最多，比如有 个任务类型的数量都是 ，那么最后一个时间单位需要放入 个不同类型的任务，所以公式变为：

2. 如果其他任务类型的数量很多，导致它们无法全部"塞入"冷却间隔中，那么最少时间就是任务总数。

因此，最终答案应该是：

算法步骤

1. 统计每种任务类型的出现次数
2. 找出出现次数最多的任务类型，及其出现次数
3. 计算出现次数等于 的任务类型数量
4. 计算 和任务总数中的较大值

这种解法的时间复杂度是 ，其中 是任务的总数。空间复杂度是 ，其中 是任务类型的数量。

对于给定的数据范围（任务列表长度和任务类型标识都不超过1000），这个解法是高效可行的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 输入获取
tasks = list(map(int, input().split(",")))
n = int(input())

# 算法实现
def solve():
    # 统计每种任务类型的数量
    cnt = {}
    for t in tasks:
        cnt[t] = cnt.get(t, 0) + 1
    
    # 找出数量最多的任务类型
    k = max(cnt.values()) if cnt else 0