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] = [enqueueTime_i, processingTime_i] means that the i^{​​​​​​th​​​​} task will be available to process at enqueueTime_i and will take processingTime_i 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]

Example: 2

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]

Output: [4,3,2,0,1]

Constraints:

• tasks.length == n
• 1 <= n <= 10 ^ 5
• 1 <= enqueueTime_i, processingTime_i <= 10 ^ 9

Approach for solving the problem:

• First of all we should see to it that if enqueue time of a task less than or equal to currentTime, then, all these tasks will be added into our available list.
• So we have to choose from the available list, some tasks that have less amount of required completion time.
• Also if many tasks have same completion time we will have to take the task with least index.
• Since we will be adding task to our available list at anytime, we use a priority queue so that when the task is added, we need not sort the array once again. Add operation in priority queue only takes logN time.

Some preprocessing:

• Since we are to consider 3 factors, i.e enqueueTime, requiredTime and index, we will add index to every tasks[i].
• Also we will sort the tasks array based on it's enqueueTime, requiredTime and index respectively. We do this so that we can get all available tasks based on its enqueueTime.

One base case to consider:

• Consider the case [[20, 20], [50, 50]].
• Here after the 0^th task gets completed, we will not be having any task in our queue.
• So we will ensure that, if our queue is empty, we will add next available task from our tasks list.

Full Code (Java): class Solution { public int[] getOrder(int[][] tasks) { // pre-processing // adding index as third element in the array for(int i = 0; i < tasks.length; i++) { int[] a = new int[3]; a[0] = tasks[i][0]; a[1] = tasks[i][1]; a[2] = i; tasks[i] = a; } // sorting array based on // 1. enqueueTime // 2. requiredTime / processingTime // 3. index Arrays.sort(tasks, new Comparator<int[]>() { @Override public int compare(int[] A, int[] B) { for(int i = 0; i < 3; i++) { if(A[i] != B[i]) { return A[i] - B[i]; } } return 0; } }); int[] arr = new int[tasks.length]; // creating priorityQueue for storing our available tasks PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() { @Override public int compare(int[] A, int[] B) { for(int i = 1; i < 3; i++) { if(A[i] != B[i]) { return A[i] - B[i]; } } return 0; } }); // initializing currentTime as time of the first available task long currentTime = tasks[0][0]; int arr_i = 0, tasks_i = 0; while(arr_i < arr.length) { while(tasks_i < tasks.length && tasks[tasks_i][0] <= currentTime) { queue.add(tasks[tasks_i++]); } // base case handling if(queue.isEmpty()) { currentTime = tasks[tasks_i][0]; queue.add(tasks[tasks_i]); tasks_i++; } int[] cur = queue.remove(); arr[arr_i++] = cur[2]; // storing index currentTime += cur[1]; } return arr; } }