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 i​​​​​​th​​​​ 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

+ Recent posts