Leet Code 1834. Single-Threaded CPU
You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei to finish processing.
You have a single-threaded CPU that can process at most one task at a time and will act in the following way:
- If the CPU is idle and there are no available tasks to process, the CPU remains idle.
- If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. - If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
- Once a task is started, the CPU will process the entire task without stopping.
- The CPU can finish a task then start a new one instantly.
Return the order in which the CPU will process the tasks.
# 시간 초과
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
ret = []
for idx, t in enumerate(tasks):
t.append(idx)
tasks = sorted(tasks, key= lambda t: t[1])
time = 1
while tasks:
for t in tasks:
if t[0] <= time:
time += t[1]
ret.append(t[2])
tasks.remove(t)
break
else:
time += 1
return ret
-> Time Complexity O(N^2)
스케쥴링 시 현재 실행 가능하며, 가장 짧은 processing time 인 task 를 골라야 함
task 를 min heap q 에 넣은(nlog(n))한 뒤, 각 선택에서 가장 짧은 실행가능한 task 고르기(log(n))
class Solution:
def getOrder(self, tasks: List[List[int]]) -> List[int]:
ret, heap= [], []
tasks = sorted([[t[0], t[1], i] for i, t in enumerate(tasks)])
time = tasks[0][0]
i = 0
while len(ret) < len(tasks):
while i < len(tasks) and tasks[i][0] <= time:
heapq.heappush(heap, (tasks[i][1], tasks[i][2]))
i += 1
if heap:
process_time, task_idx = heappop(heap)
time += process_time
ret.append(task_idx)
elif i < len(tasks):
time = tasks[i][0]
return ret
-> Time Complexity O(Nlog(N)) / Space Complexity O(N)
'Algrithm' 카테고리의 다른 글
LeetCode 128. Longest Consecutive Sequence (0) | 2023.02.26 |
---|---|
Leet Code 227. Basic Calculator II (0) | 2023.02.25 |