Single-Threaded CPU - Priority Queue - Leetcode 1834 - Python

0:00 - Read the problem
1:30 - Drawing Explanation
10:13 - Coding Explanation

leetcode 1834

#sorted #array #python

[devangishah]

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.

[shivanshtripathi]

Very good explanation sir!! I was stuggling to manage the time (specially when the cpu remains in idle state).
Thanks for the explanation.

[jonaskhanwald]

Best problem to understand Shortest job first (SJF - Non preemptive) scheduling

[mdkaranjkar]

Really nice explanation. I was wondering how could we solve this question if cpu is multithreaded

[Rahul-sqgk]

Absolutely amazing explanation. Thanks alot

[danielsun]

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

[metarus]

I got this question in an interview with Scale.

[vedantshinde]

The time complexity of this program is O(NlogN), right?

[kizhissery]

One of the hardest "Medium" in leetcode.

[anjapetrovic]

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?

[subhajitadhikary]

very nice explaination bro, keep it up, and plz make more videos!!

[gautamnaik]

@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<int[]> nextTaskProcessingTime = new PriorityQueue<int[]>((a, b) -> (a[1] - b[1]));
// Sort based on task enqueue time & task processing time.
PriorityQueue<int[]> nextTaskEnqueueTime = new PriorityQueue<int[]>((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;
store in nextTaskProcessingTime Queue
}

int currTime = 0;
int resIndex = 0;
int [] result = new int[tasks.length];

||
int sortedSingleTasks[] = null;

sortedSingleTasks = nextTaskEnqueueTime.poll();
}
else{
sortedSingleTasks =
}

result[resIndex++] = sortedSingleTasks[2];
int i = 0;
while(i < sortedSingleTasks[1]){
// while(currTime < sortedSingleTasks[1]){
if(

}
++currTime;
++i;
}

}

return result;
}
}

[research]

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.

[adityasoni]

WHat will change if you have `n` CPUs now?

[parmanandabanakar]

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.

[gunahawk]

good one but not intutive tbh i wont be able to come up this edges cases in 30 mins

[tofahub]

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<Pair<Integer, Integer>, Integer> indexMap = new HashMap<>();

for(int i = 0; i < tasks.length; i++){
Pair<Integer, Integer> pair = new Pair<Integer, Integer>(tasks[i][0], tasks[i][1]);
indexMap.put(pair, i);
}

PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<Pair<Integer, Integer>>((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<Integer, Integer> pair1 = new Pair<Integer, Integer>(tasks[taskIndex][0], tasks[taskIndex][1]);
taskIndex++;
queue.offer(pair1);
}

if(queue.isEmpty()){
time = tasks[taskIndex][0];
} else {
Pair<Integer, Integer> 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]]

[segue]

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]]?