You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimeito 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.
https://leetcode.com/problems/single-threaded-cpu/description/
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
class Solution { public int[] getOrder(int[][] tasks) { //sort Tasks based on their enqueue time //Task with minimum enqueue Time on the top of the priority queue PriorityQueue<Task> q = new PriorityQueue<>(new Comparator<Task>(){ public int compare(Task a, Task b){ int c = a.enqueueTime- b.enqueueTime; return c; } }); //Add all the tasks in a PriorityQueue for(int i=0;i<tasks.length;i++){ q.add(new Task(i, tasks[i][0], tasks[i][1])); } //Result array to return int[] res = new int[tasks.length]; //sort the tasks based on their processing time and if the processing time is equal //then use index to sort PriorityQueue<Task> pq = new PriorityQueue<>(new Comparator<Task>(){ public int compare(Task a, Task b){ int c = a.processingTime - b.processingTime; if(c==0){ c = a.id - b.id; } return c; } }); //Current Time int currTime = q.peek().enqueueTime; int j = 0; while(!q.isEmpty()){ //Add all tasks having enqueue time less than or equal to the current time while(!q.isEmpty() && q.peek().enqueueTime<= currTime){ //All available tasks @ current time pq.add(q.poll()); } //process available tasks if(!pq.isEmpty()){ Task t = pq.poll(); res[j++] = t.id; currTime = currTime+t.processingTime; } //if no task is available to process //change the current time to the enqueue time of the next available task if(!q.isEmpty() && currTime < q.peek().enqueueTime && pq.isEmpty()){ currTime = q.peek().enqueueTime; } } //process all the remaining tasks while(!pq.isEmpty()){ Task t = pq.poll(); res[j++] = t.id; } return res; } static class Task { int id; int enqueueTime; int processingTime; public Task(int id, int enqueueTime, int processingTime){ this.id = id; this.enqueueTime= enqueueTime; this.processingTime = processingTime; } public String toString(){ return this.id+":"+this.enqueueTime+":"+this.processingTime; } } } |