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.
1#include <vector>
2#include <queue>
3#include <algorithm>
4using namespace std;
5
6vector<int> getOrder(vector<vector<int>>& tasks) {
int n = tasks.size();
vector<array<int, 3>> indexedTasks(n);
for (int i = 0; i < n; ++i) {
indexedTasks[i] = {tasks[i][0], tasks[i][1], i};
}
sort(indexedTasks.begin(), indexedTasks.end());
priority_queue<array<int, 2>, vector<array<int, 2>>, greater<>> availableTasks;
vector<int> result;
long time = 0, taskIndex = 0;
while (taskIndex < n || !availableTasks.empty()) {
if (availableTasks.empty()) {
time = max(time, static_cast<long>(indexedTasks[taskIndex][0]));
}
while (taskIndex < n && indexedTasks[taskIndex][0] <= time) {
availableTasks.push({indexedTasks[taskIndex][1], indexedTasks[taskIndex][2]});
taskIndex++;
}
auto [processingTime, index] = availableTasks.top(); availableTasks.pop();
time += processingTime;
result.push_back(index);
}
return result;
}This C++ solution utilizes a priority queue to maintain tasks that can be executed based on their processing times. It sorts tasks by enqueue time and efficiently schedules tasks using the queue.