1.题目
问题描述
小C、小U、小R是工厂里的三个工人，他们互相协同制作零件。零件的制作包括三种工序："加工"、"质检"、"收尾"，分别由小C、小U、小R负责。每个零件需要多次进行"加工"和"质检"工序，但只需要进行一次"收尾"工序。每次"加工"完成后，需要进行对应的"质检"，只有当质检合格后，才可以开始下一次"加工"。当所有的"加工"和"质检"工序完成后，进行一次"收尾"工序，这样零件制作就算完成了。
小C、小U、小R的工作方式原本非常机械化，他们只能按照既定顺序一个工序一个工序地完成一个零件，比如对于一个零件的工序"加工1、质检1、加工2、质检2、收尾"，他们会按顺序逐一完成各自的任务。
老板觉得这样太低效了，于是制定了新的加工方式：小C、小U、小R之间不应该互相等待，当他们因工序等待而被阻塞时，可以直接开始新零件的加工。但是每个工序在进行中不能被打断，必须连贯地完成。
例如，有5个零件，每个零件有7道工序，分别耗时如下：
零件一：10, 10, 10, 10, 10, 10, 20
零件二：10, 10, 10, 10, 10, 10, 20
零件三：10, 10, 10, 10, 10, 10, 20
零件四：10, 10, 10, 10, 10, 10, 20
零件五：10, 10, 10, 10, 10, 10, 20
（每一行的7个数字分别表示"加工1"，"质检1"，"加工2"，"质检2"，"加工3"，"质检3"，"收尾"的耗时）
假设零件按照5、4、3、2、1的优先级开始制作，优化后的工序流程中，小C、小U、小R会更加忙碌，避免空闲。
现在给你n个零件及每个零件的工序耗时，问在经过流程优化后，所有零件加工需要花费的总时间是多少？
测试样例
样例1：
输入：n = 5, parts = [[7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20], [7, 10, 10, 10, 10, 10, 10, 20]]
输出：
200
样例2：
输入：n = 3, parts = [[5, 10, 5, 10, 5, 10], [5, 2, 4, 6, 2, 10], [3, 10, 2, 5]]
输出：
57
样例3：
输入：n = 4, parts = [[5, 7, 5, 8, 5, 7], [3, 5, 2, 7], [5, 3, 6, 4, 3, 6], [7, 7, 3, 4, 7, 3, 5, 6]]
输出：
60
2.思路
1.数据结构选择
- 每个零件的工序时间被存储在
parts数组中，其中每个零件有一个列表，第一个元素表示该零件的工序数，后续元素表示每个工序的耗时。 flag数组用来标记每个工序是否完成。我们用 0 和 1 来表示工序是否已经开始或完成。m1,m2,m3分别表示“加工”、“质检”和“收尾”阶段的结束时间。
2. 调度模拟流程
- 优先队列（堆）：我们使用一个优先队列（堆）来处理每个工序的时间。每次弹出堆中的最早时间，处理该时间点的工序，并安排下一个工序。
- 标记数组：
flag[i][j]表示第i个零件的第j个工序是否已完成。初始时所有零件的第一个工序都开始进行。
3. 工序执行顺序
- 加工工序（
m1）：如果当前时间已经过了某个零件的加工工序，我们会将其加工工序标记为完成，并将下一个加工工序安排进入队列。 - 质检工序（
m2）：如果当前时间已经过了某个零件的质检工序，我们将安排下一个质检工序。 - 收尾工序（
m3）：当某个零件的最后一个工序完成时，我们安排收尾工序进入队列。
4. 结束条件
当所有零件的工序都完成时，sum_jobs 会变为 0，意味着所有的工序已经完成，最终时间 time 就是任务结束的时间。
3.代码
import heapq
def solution(n, parts):
# Please write your code here
# 验证输入的零件数量是否与工序列表的长度一致
assert n == len(parts)
# 初始化标记数组flag，用来表示每个工序是否已完成
flag = [[0 for _ in range(len(part))] for part in parts]
# b是每个零件的工序数量（即每个零件的加工数量）
b = [part[0] for part in parts]
# sum_jobs记录尚未完成的工序数量
sum_jobs = sum(b)
# a是每个零件各个工序的耗时数据，去掉了第一个工序数量的元素
a = [part[1:] for part in parts]
# 初始化第一个工序的标记，表示所有零件的第一个工序已经开始
for i in range(n):
flag[i][0] = 1
# 初始时间为0
time = 0
# m1, m2, m3表示分别进行“加工”、“质检”和“收尾”的结束时间
m1, m2, m3 = 0, 0, 0
# last1i, last1j表示上一轮“加工”工序的零件索引和工序索引
last1i, last1j = -1, -1
# last2i, last2j表示上一轮“质检”工序的零件索引和工序索引
last2i, last2j = -1, -1
# last3i表示上一轮“收尾”工序的零件索引
last3i = -1
# 使用优先队列（堆）来处理工序的执行时间
q = []
heapq.heappush(q, 0) # 将0（初始时间）加入队列
# 当还有未完成的工序时，持续处理
while sum_jobs > 0:
time = heapq.heappop(q)
# 处理所有在相同时间点需要处理的工序
while q and q[0] == time:
heapq.heappop(q)
# 如果当前时间为m3（“收尾”时间），且有待收尾的工序，则减少未完成工序数量
if time == m3 and last3i != -1:
sum_jobs -= 1
# 如果当前时间为m2（“质检”时间），且质检工序未完成，则开始下一个质检工序
if time == m2 and last2i != -1 and last2j != -1:
flag[last2i][last2j + 1] = 1 # 标记该零件的质检工序已完成
sum_jobs -= 1 # 完成一个工序，减少未完成的工序数量
# 如果当前时间大于等于m1（“加工”时间），尝试安排新的加工工序
if time >= m1:
if time == m1 and last1i != -1 and last1j != -1:
flag[last1i][last1j + 1] = 1 # 标记加工工序已完成
sum_jobs -= 1 # 完成一个工序，减少未完成的工序数量
# 查找下一个可以进行的加工工序
found = False
for i in range(n):
for j in range(0, b[i], 2): # 偶数索引表示加工工序
if flag[i][j] == 1 and j != b[i] - 1: # 检查工序是否已完成
temi, temj = i, j
flag[temi][temj] = 0 # 标记该工序已开始
m1 = time + a[temi][temj] # 计算新的加工结束时间
last1i, last1j = temi, temj # 记录最新加工工序的位置
heapq.heappush(q, m1) # 将加工结束时间加入队列
found = True
break
if found:
break
# 如果当前时间大于等于m2（“质检”时间），尝试安排新的质检工序
if time >= m2:
found = False
for i in range(n):
for j in range(1, b[i], 2):
if flag[i][j] == 1:
temi, temj = i, j
flag[temi][temj] = 0
m2 = time + a[temi][temj]
last2i, last2j = temi, temj
heapq.heappush(q, m2)
found = True
break
if found:
break
# 如果当前时间大于等于m3（“收尾”时间），开始安排收尾工序
if time >= m3:
for i in range(n):
if flag[i][b[i] - 1] == 1:
temi = i
flag[temi][b[temi] - 1] = 0 # 标记收尾工序已开始
m3 = time + a[temi][b[temi] - 1]
last3i = temi
heapq.heappush(q, m3)
break
return time
if __name__ == "__main__":
# You can add more test cases here
parts1 = [[7, 10, 10, 10, 10, 10, 10, 20],
[7, 10, 10, 10, 10, 10, 10, 20],
[7, 10, 10, 10, 10, 10, 10, 20],
[7, 10, 10, 10, 10, 10, 10, 20],
[7, 10, 10, 10, 10, 10, 10, 20]]
parts2 = [[5, 10, 5, 10, 5, 10],
[5, 2, 4, 6, 2, 10],
[3, 10, 2, 5]]
print(solution(5, parts1) == 200)
print(solution(3, parts2) == 57)
heapq 是 Python 内置的一个模块，用于实现堆（heap）数据结构，堆是一种二叉树结构，满足“堆序性质”，可以高效地获取最小（或最大）元素。heapq 模块实现的是一个最小堆（min-heap），即堆顶元素总是最小的。
主要功能
- 堆的插入和删除：通过
heapq提供的函数，可以轻松地维护一个堆，支持插入、删除、获取最小元素等操作。 - 优先队列：由于堆可以高效地获取最小元素，所以它通常用于实现优先队列（priority queue），例如在你提供的代码中，堆用于存储和处理不同时间点的工序。
常用函数
-
heapq.heappush(heap, item)向堆中插入一个元素，并保持堆的性质。
heap：堆数据结构（列表）item：要插入的元素
import heapq heap = [1, 3, 5, 7, 9, 2] heapq.heappush(heap, 4) print(heap) # 输出 [1, 3, 2, 7, 9, 5, 4] -
heapq.heappop(heap)从堆中弹出并返回最小的元素，并重新保持堆的性质。
- 返回堆中的最小元素，且移除该元素。
import heapq heap = [1, 3, 5, 7, 9, 2] print(heapq.heappop(heap)) # 输出 1 print(heap) # 输出 [2, 3, 5, 7, 9] -
heapq.heappushpop(heap, item)向堆中插入元素，然后立即弹出并返回堆中最小的元素。这个操作比先插入然后再弹出要高效。
import heapq heap = [1, 3, 5, 7, 9, 2] print(heapq.heappushpop(heap, 4)) # 输出 1，4 被插入后 1 被弹出 print(heap) # 输出 [2, 3, 4, 7, 9, 5] -
heapq.heapify(iterable)将一个可迭代对象转换成堆。
iterable：可以是列表、元组等，转化为堆结构。
import heapq heap = [5, 7, 9, 1, 3, 2] heapq.heapify(heap) print(heap) # 输出 [1, 3, 2, 7, 5, 9] -
heapq.nlargest(n, iterable)获取
iterable中最大的n个元素。n：需要返回的元素个数iterable：可以是任何可迭代对象
import heapq nums = [1, 3, 5, 7, 9, 2] print(heapq.nlargest(3, nums)) # 输出 [9, 7, 5] -
heapq.nsmallest(n, iterable)获取
iterable中最小的n个元素。n：需要返回的元素个数iterable：可以是任何可迭代对象
import heapq nums = [1, 3, 5, 7, 9, 2] print(heapq.nsmallest(3, nums)) # 输出 [1, 2, 3]
