### shahianshu's blog

By shahianshu, history, 12 months ago, ,

hello , i am getting wa for my code of the problem round robin scheduling , I have tried many test case I couldn't come up with a test case where my code fails.

MY APPROACH :- i have made an observation that for each task Ti it will become zero only at an iteration equal to Ti . For example, suppose Ti = 9 then this element will become zero at the 9th iteration irrespective of all the other tasks . So i thought that i need to just sort the array based on the value of Ti and then the smallest value Ti will be the one going 1st and then all the Ti's whose values are greater than it . So , i kept two values in the vector , first :- value of Ti , and second :- index of particular Ti . Now i sorted the vector , if values of some element a and b are equal then i sort them in increasing order of index. I also maintained a binary indexed tree denoted by bit[] , this is used to tell me how many total tasks are still present before a particular element.

MY SOLUTION( i have commented each and every part ) :- link

UPDATE :- MY EDITED SOLUTION :- link

• -12

 » 12 months ago, # |   0 You code with unpleasant anti-symmetric formatting, so I won't read your code.Next time, do it properly. Like this... // This is readable and aesthetic void function_or_whatever(type parameter...) { // do something here return; } 
•  » » » 12 months ago, # ^ | ← Rev. 19 →   0 Please trace the scheduling loop in solution1() and solution2() functions of the following code using the automatically generated counterexample to find out where exactly your solution produces different elapsed time for some task(s). You may run the same code to find more counterexamples if you wish. Note that starting with the set of tasks { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 } in the shown counterexample106 10 1 7 6 10 1 10 2 1the set of pending tasks after the Round-Robin scheduling iterations should be: After iteration 1: { 1, 2, 4, 5, 6, 8, 9 }, as tasks { 3, 7, 10 } would have just been completed. After iteration 2: { 1, 2, 4, 5, 6, 8 }, as task { 9 } would have just been completed. After iteration 6: { 2, 4, 6, 8 }, as tasks { 1, 5 } would have just been completed. After iteration 7: { 2, 6, 8 }, as task { 4 } would have just been completed. After iteration 10: { } "an empty set", as tasks { 2, 6, 8 } would have just been completed. After iterations 3, 4, 5, 8 and 9, the size of the pending task set should not change, as no tasks have been completed during any of these iterations. Therefore, the following sequence is the size of pending task set after Round-Robin scheduling of this counterexample. 7, 6, 6, 6, 6, 4, 3, 3, 3, 0Note also that in each iteration, the rank of processing some particular task may be decrement if other tasks which precede it have been completed in the previous iteration, and have therefore been removed from the set. For example, the rank of processing task 4 should be: 4 in iteration { 1 }, the initial rank 3 in iterations { 2, 3, 4, 5, 6 }, as task 3 has been completed in iteration 1 2 in iterations { 7 }, as task 1 has been completed in iteration 6 The rank of each task in the last iteration in which its processing time is completed determines exactly the elapsed time of this task relative to the starting time of such iteration.