Parallel Courses Iii - Leetcode Solution

Problem Statement:

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 consume then the CPU remains idle. If the CPU is idle and there are available tasks, then the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time then it will choose the task with the smallest index. Once a task is started, the CPU will execute 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:

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.

Solution:

The problem is a classic example of priority queue application. If we maintain a priority queue and arrange the tasks in the order of their enqueue starting time, processing time and task index, we can achieve the desired output. Here is how we can solve the problem:

First, we need to sort the array of tasks according to their enqueue time. This way, we will have a queue of tasks that are waiting to be executed.

We also need to create a priority queue that stores the tasks based on their processing time and task index.

Now, we need to start going through the queue of waiting tasks. For each task that is waiting:

If the CPU is idle, we take the first task from the queue, execute it and save the end time of the execution in the result vector.

If the CPU is not idle, we put the task into the priority queue.

Then, we need to check the priority queue. If it is not empty, we need to choose and execute the task that has the shortest processing time and the lowest index. Here, we execute one task at a time and save the result into the result vector.

We continue until there are no more tasks waiting to be executed.

Code:

Here's the Python 3 implementation of the above solution:

from queue import PriorityQueue

def get_order(tasks:List[List[int]])->List[int]:

n = len(tasks)
result = []
task_queue = PriorityQueue()
tasks.sort()

current_time = 0
current_task = 0

while len(result)<n:
    
    if not len(task_queue) and current_task<n:
        current_time = tasks[current_task][0]
        
    while current_task<n and tasks[current_task][0] == current_time:
        task_queue.put((tasks[current_task][1], tasks[current_task][0], current_task))
        current_task += 1
        
    if len(task_queue):
        processing_time, enqueue_time, task_index = task_queue.get()
        result.append(task_index)
        current_time += processing_time
        
return result

Time Complexity:

The time complexity of this solution is O(n log n). This is because of the priority queue data structure that we are using. It has a log n time complexity, which is the reason why our algorithm has the same time complexity.

1