Hi, very good explanation and I got this type of similar question in my Google interview, and I couldn't come up with the optimal solution. But won't give up and will keep coding!!! Hats off to your solution though.
for i, t in enumerate(tasks): t.append(i) tasks.sort(key=lambda t: t[0]) res, minHeap = [], [] i, time = 0, tasks[0][0] for _ in range(len(tasks)): if not minHeap: time = max(time, tasks[i][0]) while i < len(tasks) and time >= tasks[i][0]: heapq.heappush(minHeap, [tasks[i][1], tasks[i][2]]) i += 1 procTime, index = heapq.heappop(minHeap) time += procTime res.append(index) return res
What if there is a gap between the two job sequences. For example: if 1st job sequence end at say 4th second, the job scheduler will look for other jobs which might start from or before 4 seconds given that the queue is empty. Now my the confusion arises if the nearest job starts at 6th seconds. Can you clarify how can I plan to handle this case? Here is an example input vector: [[1,3], [6,2], [8,3]], 1st job is going to end at second 4 and the second job will start not before 6th second.
@neetcode I had a doubt on this problem set the whole point was to process the Task in a way that they require less amount of time right?? I have developed a two-pointer solution that fails for the below test case Input tasks = [[19,13],[16,9],[21,10],[32,25],[37,4],[49,24],[2,15],[38,41],[37,34],[33,6],[45,4],[18,18],[46,39],[12,24]] Expected Output [6,1,2,9,4,10,0,11,5,13,3,8,12,7] Total time According to this output is 268 My Solution Output [6,4,10,9,1,2,0,11,13,5,3,8,12,7] Total time According to this output is 238 My code Basically, there is one major/incoming queue nextTaskEnqueueTime specifying what would the next task to take and a minor queue which keeps track of all the task received in that period when the first task was received and sorted on the processing time so that the CPU can select the next shortest processing time task from it, till this minor doesn't get empty we take the next task it from this queue also while processing we add the task from major/incoming queue Is my thought process wrong??.. can you please have a look into this .. or anyone else my code below class Solution { public int[] getOrder(int[][] tasks) { //Sort based on task processing time. PriorityQueue nextTaskProcessingTime = new PriorityQueue((a, b) -> (a[1] - b[1])); // Sort based on task enqueue time & task processing time. PriorityQueue nextTaskEnqueueTime = new PriorityQueue((a, b) -> (a[0] != b[0] ? (a[0] - b[0]) : (a[1] - b[1]))); // Store task enqueue time, processing time, index. int sortedTasks[][] = new int[tasks.length][3]; for (int i = 0; i < tasks.length; ++i) { sortedTasks[i][0] = tasks[i][0]; sortedTasks[i][1] = tasks[i][1]; sortedTasks[i][2] = i; nextTaskEnqueueTime.add(sortedTasks[i]);// store in nextTaskProcessingTime Queue } int currTime = 0; int resIndex = 0; int [] result = new int[tasks.length]; while(!nextTaskEnqueueTime.isEmpty() || !nextTaskProcessingTime.isEmpty()){ int sortedSingleTasks[] = null; if(nextTaskProcessingTime.isEmpty()){ sortedSingleTasks = nextTaskEnqueueTime.poll(); } else{ sortedSingleTasks = nextTaskProcessingTime.poll(); } result[resIndex++] = sortedSingleTasks[2]; int i = 0; while(i < sortedSingleTasks[1]){ // while(currTime < sortedSingleTasks[1]){ if( !nextTaskEnqueueTime.isEmpty()){ nextTaskProcessingTime.add(nextTaskEnqueueTime.poll()); } ++currTime; ++i; } } return result; } }
How is this condition taken care? "If multiple tasks have the same shortest processing time, it will choose the task with the smallest index". Does the minHeap automatically takes care of it, since you have the task number as the 2nd element.
Heap always keep the root as either the smallest or largest value/node (min Heap or max Heap respectively, there's more details about why it's like this but this is always the case). In Python, the implementation of heap is always min heap and so when you pop from the heap, it is always the smallest node guaranteed. So in a way, yea minHeap in Python automatically handles this case for you
How does heapq.heappush know that the array of tasks added to the heap should have its priority based on the task's index since there are 2 values in the array -- [tasks[i][1], tasks[i][2]]?
I've figured this out. Thanks. Got the answer from a guy called rowe1227 on leetcode: The heap is comparing the two tuples to see which one is less than the other. So if the first element of both tuples (the processing time) are equal, then it will compare the second element in each tuple (the index).
Hi, very good explanation and I got this type of similar question in my Google interview, and I couldn't come up with the optimal solution. But won't give up and will keep coding!!!
Hats off to your solution though.
for i, t in enumerate(tasks):
t.append(i)
tasks.sort(key=lambda t: t[0])
res, minHeap = [], []
i, time = 0, tasks[0][0]
for _ in range(len(tasks)):
if not minHeap:
time = max(time, tasks[i][0])
while i < len(tasks) and time >= tasks[i][0]:
heapq.heappush(minHeap, [tasks[i][1], tasks[i][2]])
i += 1
procTime, index = heapq.heappop(minHeap)
time += procTime
res.append(index)
return res
Very good explanation sir!! I was stuggling to manage the time (specially when the cpu remains in idle state).
Thanks for the explanation.
One of the hardest "Medium" in leetcode.
Best problem to understand Shortest job first (SJF - Non preemptive) scheduling
Really nice explanation. I was wondering how could we solve this question if cpu is multithreaded
import threading
/s
The time complexity of this program is O(NlogN), right?
This is really neat!! Thank you.
where do we accounted for sorting elements when they are both available but we are taking the one that takes the less time to execute?
I got this question in an interview with Scale.
Absolutely amazing explanation. Thanks alot !!!!!!
love your adding index trick! clever!
What if there is a gap between the two job sequences. For example: if 1st job sequence end at say 4th second, the job scheduler will look for other jobs which might start from or before 4 seconds given that the queue is empty. Now my the confusion arises if the nearest job starts at 6th seconds. Can you clarify how can I plan to handle this case? Here is an example input vector: [[1,3], [6,2], [8,3]], 1st job is going to end at second 4 and the second job will start not before 6th second.
Got the answer. Thanks
best explanation Buddy
WHat will change if you have `n` CPUs now?
Very good explaination
very nice explaination bro, keep it up, and plz make more videos!!
Thanks, happy it was helpful 🙂
@neetcode
I had a doubt on this problem set the whole point was to process the Task in a way that they require less amount of time right??
I have developed a two-pointer solution that fails for the below test case
Input
tasks = [[19,13],[16,9],[21,10],[32,25],[37,4],[49,24],[2,15],[38,41],[37,34],[33,6],[45,4],[18,18],[46,39],[12,24]]
Expected Output
[6,1,2,9,4,10,0,11,5,13,3,8,12,7] Total time According to this output is 268
My Solution Output
[6,4,10,9,1,2,0,11,13,5,3,8,12,7] Total time According to this output is 238
My code
Basically, there is one major/incoming queue nextTaskEnqueueTime specifying what would the next task to take and a minor queue which keeps track of
all the task received in that period when the first task was received and sorted on the processing time so that the CPU can select the next shortest processing time task from it, till this minor doesn't get empty we take the next task it from this queue also while processing we add the task from major/incoming queue
Is my thought process wrong??.. can you please have a look into this .. or anyone else
my code below
class Solution {
public int[] getOrder(int[][] tasks) {
//Sort based on task processing time.
PriorityQueue nextTaskProcessingTime = new PriorityQueue((a, b) -> (a[1] - b[1]));
// Sort based on task enqueue time & task processing time.
PriorityQueue nextTaskEnqueueTime = new PriorityQueue((a, b) -> (a[0] != b[0] ? (a[0] - b[0]) : (a[1] - b[1])));
// Store task enqueue time, processing time, index.
int sortedTasks[][] = new int[tasks.length][3];
for (int i = 0; i < tasks.length; ++i) {
sortedTasks[i][0] = tasks[i][0];
sortedTasks[i][1] = tasks[i][1];
sortedTasks[i][2] = i;
nextTaskEnqueueTime.add(sortedTasks[i]);// store in nextTaskProcessingTime Queue
}
int currTime = 0;
int resIndex = 0;
int [] result = new int[tasks.length];
while(!nextTaskEnqueueTime.isEmpty() || !nextTaskProcessingTime.isEmpty()){
int sortedSingleTasks[] = null;
if(nextTaskProcessingTime.isEmpty()){
sortedSingleTasks = nextTaskEnqueueTime.poll();
}
else{
sortedSingleTasks = nextTaskProcessingTime.poll();
}
result[resIndex++] = sortedSingleTasks[2];
int i = 0;
while(i < sortedSingleTasks[1]){
// while(currTime < sortedSingleTasks[1]){
if( !nextTaskEnqueueTime.isEmpty()){
nextTaskProcessingTime.add(nextTaskEnqueueTime.poll());
}
++currTime;
++i;
}
}
return result;
}
}
How is this condition taken care? "If multiple tasks have the same shortest processing time, it will choose the task with the smallest index".
Does the minHeap automatically takes care of it, since you have the task number as the 2nd element.
Heap always keep the root as either the smallest or largest value/node (min Heap or max Heap respectively, there's more details about why it's like this but this is always the case). In Python, the implementation of heap is always min heap and so when you pop from the heap, it is always the smallest node guaranteed. So in a way, yea minHeap in Python automatically handles this case for you
best explanation
LOVE IT!
good one but not intutive tbh i wont be able to come up this edges cases in 30 mins
Good
Is that a Jojo reference 15:45 ?
How does heapq.heappush know that the array of tasks added to the heap should have its priority based on the task's index since there are 2 values in the array -- [tasks[i][1], tasks[i][2]]?
I've figured this out. Thanks.
Got the answer from a guy called rowe1227 on leetcode:
The heap is comparing the two tuples to see which one is less than the other. So if the first element of both tuples (the processing time) are equal, then it will compare the second element in each tuple (the index).
@@segue97: thanks, you saved my day
This code is failing this test case for me. I really don't see why
class Solution {
public int[] getOrder(int[][] tasks) {
int [] result = new int[tasks.length];
Map indexMap = new HashMap();
for(int i = 0; i < tasks.length; i++){
Pair pair = new Pair(tasks[i][0], tasks[i][1]);
indexMap.put(pair, i);
}
PriorityQueue queue = new PriorityQueue((a, b) -> {
if(a.getValue() == b.getValue()){
return indexMap.get(a) - indexMap.get(b);
}
return a.getValue() - b.getValue();
});
Arrays.sort(tasks, (a, b) -> {
return a[0] - b[0];
});
int index = 0, time = tasks[0][0], taskIndex = 0;
while(!queue.isEmpty() || taskIndex < tasks.length){
while(taskIndex < tasks.length && time >= tasks[taskIndex][0]){
Pair pair1 = new Pair(tasks[taskIndex][0], tasks[taskIndex][1]);
taskIndex++;
queue.offer(pair1);
}
if(queue.isEmpty()){
time = tasks[taskIndex][0];
} else {
Pair curr = queue.poll();
result[index++] = indexMap.get(curr);
time += curr.getValue();
}
}
return result;
}
}
[[142,185],[142,74],[669,253],[669,953],[669,694],[669,474],[669,839],[457,87],[457,371],[457,510],[457,691],[457,237],[457,225],[457,413],[457,935],[457,703],[669,709],[669,18],[669,687],[669,911],[669,741],[669,526],[669,900],[669,842],[767,624],[767,802],[287,690],[287,438],[287,406],[287,561],[287,518],[287,769],[287,709],[107,420],[107,277],[107,119],[107,28],[894,373],[894,592],[894,698],[894,947],[894,120],[894,296],[894,429],[894,792],[894,677],[13,6],[13,551],[13,85],[13,930],[13,749],[13,195],[13,629],[13,481],[13,873],[669,324],[669,659],[366,76],[366,385],[366,437],[366,72],[366,518],[366,7],[366,454],[366,382],[366,128],[366,134],[21,824],[21,5],[88,156],[88,331],[88,698],[88,595],[88,403],[380,607],[292,771],[292,323],[292,17],[292,712],[292,202],[292,183],[860,13],[860,632],[860,816],[860,890],[860,179],[860,873],[860,969],[860,960],[860,155],[128,796],[128,582],[128,978],[128,255]]