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.
1from heapq import heappop, heappush
2
3def getOrder(tasks):
4 indexed_tasks = sorted([(t[0], t[1], i) for i, t in enumerate(tasks)])
5 result = []
6 available_tasks = []
7 time = 0
8 i = 0
9 while i < len(tasks) or available_tasks:
10 if not available_tasks:
11 time = max(time, indexed_tasks[i][0])
12 while i < len(tasks) and indexed_tasks[i][0] <= time:
13 heappush(available_tasks, (indexed_tasks[i][1], indexed_tasks[i][2]))
14 i += 1
15 processing_time, index = heappop(available_tasks)
16 time += processing_time
17 result.append(index)
18 return resultThe function starts by sorting tasks with indices by their enqueue time, then iteratively adds tasks to a heap that are available at the current time. It processes tasks based on the heap, which optimizes the selection of the shortest available task, ensuring tasks are processed efficiently.
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.