KK's blog

每天积累多一些

0%

LeetCode 1834 Single-Threaded CPU

Posted on Disqus:

LeetCode



You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTime<sub>i</sub>, processingTime<sub>i</sub>] means that the i<sup>​​​​​​th</sup>​​​​ task will be available to process at enqueueTime<sub>i</sub> and will take processingTime<sub>i</sub>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.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.


Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation**: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.
Constraints:*​​​​​​​ 1 <= tasks.length <= 10<sup>5</sup>
tasks[i] = [enqueueTime<sub>i</sub>, processingTime<sub>i</sub>] 1 <= enqueueTime<sub>i</sub>, processingTime<sub>i</sub> <= 10<sup>9</sup>

题目大意：

一个CPU按一定顺序单线程处理多个当前准备好的任务。准备好的任务排序是按处理时间为先，然后是下标。

解题思路：

这题跟L253 Meeting Rooms II类似也是关于重合区间的问题

  1. 先对开始时间进行排序
  2. 对endtime进行heap排序，用start跟堆顶比较
    但区别是endtime不是预先知道的，是根据前面任务完成时间而动态计算。所以heap应该严格根据题目要求，存储处理时间和任务下标。
    入堆条件为新任务开始时间 <= 当前任务的结束时间
    这里注意有两种情况需要考虑：
  3. 区间重合
  4. 区间不重合 （容易忽略）
    Current_time的引入=连续区间的开始时间(不重合的区间)或结束时间(存在重合的区间不会记录开始时间到这个变量)。

解题步骤：

  1. 任务按开始时间排序
  2. 建堆，堆元素是(processing time, task index)
  3. 入堆条件是遍历后序任务，若新任务开始时间 <= 当前任务的结束时间，才入堆
  4. 出堆得到任务下标，加入到结果序列

注意事项：

  1. 任务排序时候，记得加入index以及之后都要用此变量，不能用原输入变量
  2. 严格按照条件：堆元素为存储处理时间和任务下标，不能用Endtime
  3. 两个不同情况：区间重合或不重合，写程序要重点考虑。
  4. 程序可以优化：heappush的3个逻辑是重复的，合并为一个，current_time可以为开始时间，这样就可以把多个同一个开始时间的tasks一起加入到堆
  5. if not heap, 计算current_time也是两情况，若两区间重合情况，current_time是第一个出堆时区间结束时间，它大于第二区间的开始时间，时间不能回拨，所以取max。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def getOrder(self, tasks: List[List[int]]) -> List[int]:
	sorted_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(len(tasks))]
	sorted_tasks.sort()
	heap, res = [], []
	current_time = sorted_tasks[0][0]
	i = 0
	while heap or i < len(sorted_tasks):
		if not heap:
			current_time = max(current_time, sorted_tasks[i][0])
		while i < len(sorted_tasks) and sorted_tasks[i][0] <= current_time: # start time <= current task's finished time, task[0]-> current_time 
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) 
			i += 1

		task = heapq.heappop(heap)
		current_time += task[0]
		res.append(task[1]) # finished processing

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n)

Python代码(中间代码)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def getOrder(self, tasks: List[List[int]]) -> List[int]:
	sorted_tasks = [(tasks[i][0], tasks[i][1], i) for i in range(len(tasks))]
	sorted_tasks.sort()
	heap, res = [], []
	current_time = sorted_tasks[0][0]
	i = 0
	while i < len(sorted_tasks):
		if i > 0 and sorted_tasks[i-1][0] != sorted_tasks[i][0]:
			break
		heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) # finished time=>processing t, task index #3
		i += 1
	while heap or i < len(sorted_tasks):
		if not heap:
			current_time = sorted_tasks[i][0]
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2]))
			i += 1

		task = heapq.heappop(heap)
		current_time += task[0]
		res.append(task[1]) # finished processing
		while i < len(sorted_tasks) and sorted_tasks[i][0] <= current_time: # start time <= current task's finished time, task[0]-> current_time 
			heapq.heappush(heap, (sorted_tasks[i][1], sorted_tasks[i][2])) 
			i += 1
	return res
Free mock interview