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# 初始时间为0time = 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 = Falsefor 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, jflag[temi][temj] = 0 # 标记该工序已开始m1 = time + a[temi][temj] # 计算新的加工结束时间last1i, last1j = temi, temj # 记录最新加工工序的位置heapq.heappush(q, m1) # 将加工结束时间加入队列found = Truebreakif found:break# 如果当前时间大于等于m2（“质检”时间），尝试安排新的质检工序if time >= m2:found = Falsefor i in range(n):for j in range(1, b[i], 2):if flag[i][j] == 1:temi, temj = i, jflag[temi][temj] = 0m2 = time + a[temi][temj]last2i, last2j = temi, temjheapq.heappush(q, m2)found = Truebreakif found:break# 如果当前时间大于等于m3（“收尾”时间），开始安排收尾工序if time >= m3:for i in range(n):if flag[i][b[i] - 1] == 1:temi = iflag[temi][b[temi] - 1] = 0 # 标记收尾工序已开始m3 = time + a[temi][b[temi] - 1]last3i = temiheapq.heappush(q, m3)breakreturn timeif __name__ == "__main__":# You can add more test cases hereparts1 = [[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]
