Sponsored
Sponsored
This approach involves using a priority queue (or min-heap) to efficiently select the task with the shortest processing time. We will first sort the tasks based on their enqueue time. At each step, we'll enqueue tasks that are available and select the task with the shortest processing time for execution using the priority queue. This ensures optimal selection and execution of tasks, minimizing wait times.
Time Complexity: O(n log n) due to sorting and heap operations. Space Complexity: O(n) for storing tasks and heap.
1function getOrder(tasks) {
2 tasks = tasks.map((task, index) => [...task, index]);
3 tasks.sort((a, b) => a[0] - b[0]);
4 const result = [];
5 const availableTasks = [];
6 let time = 0, i = 0;
7 while (i < tasks.length || availableTasks.length) {
8 if (!availableTasks.length) {
9 time = Math.max(time, tasks[i][0]);
10 }
11 while (i < tasks.length && tasks[i][0] <= time) {
12 availableTasks.push(tasks[i]);
13 i++;
14 }
15 availableTasks.sort((a, b) => {
16 if (a[1] === b[1]) return a[2] - b[2];
17 return a[1] - b[1];
18 });
19 const [_, processingTime, index] = availableTasks.shift();
20 time += processingTime;
21 result.push(index);
22 }
23 return result;
24}This JavaScript solution leverages manual sorting of an array to simulate a priority queue. Tasks are processed by sorting available tasks by processing time and index each time a task is to be executed, ensuring efficient task management.
This approach uses a structure like TreeMap (or Multimap) that supports ordering key-value pairs. It allows us to keep the tasks ordered by enqueue times and quickly find tasks that should start processing.
Time Complexity: O(n log n) because of sorting and the priority queue operations. Space Complexity: O(n) for storage.
1import java.util.*;
2
3This Java solution uses a priority queue to keep track of available tasks by shortest processing time. It simulates task execution using an index-based list to ensure tasks are queried efficiently.