각 항목이 다른 작업 유형을 나타내는 작업이라고 하는 정수 목록이 있다고 가정하고 k라고 하는 음이 아닌 정수도 있습니다. 각 작업은 완료하는 데 한 단위의 시간이 걸리고 작업은 올바른 순서로 완료되어야 하지만 두 개의 동일한 유형 작업을 수행하는 사이에는 k 단위의 시간이 있어야 합니다. 언제든지 작업을 수행하거나 기다릴 수 있습니다. 모든 작업을 완료하는 데 걸리는 시간을 찾아야 합니다.
따라서 입력이 task =[0, 1, 1, 2] k =2와 같으면 출력은 6이 됩니다. 처음 두 작업은 유형이 다르기 때문에 간격 없이 실행할 수 있습니다. 2, 다음 작업은 동일한 유형의 작업이므로 2번 슬롯을 기다린 다음 작업을 수행하고 마지막으로 다른 유형의 작업을 갖게 됩니다. 유형 2. 그래서 이 작업을 수행합니다. 따라서 [0, 1, wait, wait, 1, 2]와 같습니다. 이를 통해 6개의 시간 슬롯이 필요함을 확인할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 틱 :=0
- 슬롯:=새 지도
- 작업의 각 t에 대해 다음을 수행합니다.
- tf :=슬롯[t] t가 슬롯에 있는 경우
- tf가 null이 아니고 tf - 틱> 0이면
- 틱 :=틱 + tf - 틱
- 틱 :=틱 + 1
- 슬롯[t] :=틱 + k
- 반환 틱
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(tasks, k):
tick = 0
slot = {}
for t in tasks:
tf = slot.get(t)
if tf is not None and tf - tick > 0:
tick += tf - tick
tick += 1
slot[t] = tick + k
return tick
tasks = [0, 1, 1, 2]
k = 2
print(solve(tasks, k)) 입력
[0, 1, 1, 2]
출력
6