1834_单线程_CPU

类型：堆

• 1834. 单线程 CPU 💛

  https://leetcode-cn.com/problems/single-threaded-cpu/

  ❓ 数组 task 存储了编号从 0 到 n-1 的 n 项任务。tasks[i] = [enqueueTime, processingTime] 表明了该项任务的开始时间和任务耗时分别是 enqueueTime 和 processingTime。

  现有一个单线程 CPU，当 CPU 处于空闲，且有任务可执行时，CPU 会选择可执行任务中耗时最短的任务执行。

  💡 堆

  我们用一个小顶堆来维护当前可执行的任务，以任务耗时作为比较键。当 CPU 空闲时，我们从堆顶取出任务，执行该任务，并将该任务执行期间将会产生的新任务都加入堆。

  class Solution:
      def getOrder(self, tasks: List[List[int]]) -> List[int]:
          n = len(tasks)
          for i in range(n):
              tasks[i].append(i)
              tasks[i][1], tasks[i][2] = tasks[i][2], tasks[i][1]
          tasks.sort()
          ans = []
          heap = []
          end = tasks[0][0]
          i = 0
          while i < n and tasks[i][0] <= tasks[0][0]:
              heapq.heappush(heap, (tasks[i][2], tasks[i][1], tasks[i][0]))
              i += 1
          while heap or i < n:
              if heap:
                  processing, index, start = heapq.heappop(heap)
                  ans.append(index)
                  end += processing
              else:
                  end = tasks[i][0]
              while i < n and tasks[i][0] <= end:
                  heapq.heappush(heap, (tasks[i][2], tasks[i][1], tasks[i][0]))
                  i += 1
          return ans