easyQueuePattern: Design
Process Task Scheduling Solution
Problem Statement
Implement a system to schedule tasks based on their priority and arrival order. You are given a list of tasks, where each task has a unique identifier and a priority level. Tasks should be processed in descending order of priority. If two tasks have the same priority, the task that arrived earlier should be processed first. Return the sequence of task identifiers in the order they are processed.
Examples
Example 1:
Input:[[1, 2], [2, 1], [3, 2], [4, 3]]
Output:[4, 1, 3, 2]
Explanation: Tasks are (ID, Priority): (1, 2), (2, 1), (3, 2), (4, 3). Task 4 has the highest priority (3). Task 1 and Task 3 have the next highest priority (2). Task 1 arrived before Task 3, so Task 1 is processed before Task 3. Task 2 has the lowest priority (1). The processing order is Task 4, Task 1, Task 3, Task 2. The output is [4, 1, 3, 2].
Example 2:
Input:[[10, 5], [20, 5], [30, 1], [40, 5]]
Output:[10, 20, 40, 30]
Explanation: Tasks are (ID, Priority): (10, 5), (20, 5), (30, 1), (40, 5). Tasks 10, 20, and 40 all have the highest priority (5). They arrived in the order 10, 20, 40. Task 30 has the lowest priority (1). The processing order is Task 10, Task 20, Task 40, Task 30. The output is [10, 20, 40, 30].
Example 3:
Input:[[1, 1]]
Output:[1]
Explanation: There is only one task. The processing order is Task 1. The output is [1].
Constraints
- The number of tasks will be between 0 and 1000.
- Task identifiers will be unique integers between 1 and 10^9.
- Task priorities will be integers between 1 and 10.
- The input list contains lists, where each inner list has exactly two elements: [task_id, priority].
Time: O(N log N) Space: O(N)
Use a priority queue data structure. Store tasks in the priority queue, ordered by priority (descending) and then by arrival order (ascending). The arrival order can be maintained using an index or a timestamp. Dequeue elements one by one to get the processed task sequence.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import heapq
def process_task_scheduling(tasks):
if not tasks:
return []
# The heap will store tuples: (-priority, arrival_order, task_id)
# We use -priority because heapq is a min-heap, and we want max priority first.
# arrival_order is the index, smaller index means earlier arrival.
pq = []
for i, (task_id, priority) in enumerate(tasks):
heapq.heappush(pq, (-priority, i, task_id))
processed_order = []
while pq:
neg_priority, arrival_order, task_id = heapq.heappop(pq)
processed_order.append(task_id)
return processed_order