Re: [algogeeks] Round Robin Schedulling Problem
L[i] tells how many elements D[j] less than D[i] such that j < i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));
rem = n;
curtime = 0;
last = 0;
for (i = 0; i < n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
curtime += (D[i] - last) * rem;
i++;
rem--;
while (i < n && D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]] + 1; i++;
rem--;
}
last = d[i-1];
}
curtime = total time till the iteration in which last event(which has burst
time just less than current event) has been completed.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
yes, i agree, and that is why i called my soln as naive,
i want to understand the logic for the solution(wht interval tree, what is
done inside the for loop with ans assignmetn) because no one can go and
write this solution in an interview without an explanation :)
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, May 26, 2011 at 6:07 AM, Anand wrote:
> @Ashish: complexity for your solution is O(n*Total seconds)
>
>
>
> On Wed, May 25, 2011 at 5:25 PM, Ashish Goel wrote:
>
>> Hi
>>
>> I was just thinking of a simpler solution
>>
>> find sum of the time all processes will take, lets call that sum, say for
>> 8,1,3,3,8 it is 23
>> walk over each process to see if this has been completely executed, if not
>> set the out[i]=curTime and reduce the T[i] by 1.(out is the process final
>> end time and T is the time process will take if run without halt i.e.
>> 8,1,3,3,8)
>>
>> t=0;
>> while (t<=sum)
>> {
>>
>> for (int i=0;i>{
>> if (T[i]>0) {t++; out[i]=t; T[i]--;}
>>}
>> }
>>
>> I must say that this is naive solution
>>
>> I am not able to understand how interval tree and the code given
>> by anshumishra6827 will work. Even if this is right, what was the rationale
>> for using segment tree and what is the loop doing by playing with ans, D,
>> L..
>>
>> Best Regards
>> Ashish Goel
>> "Think positive and find fuel in failure"
>> +919985813081
>> +919966006652
>>
>>
>> On Wed, May 25, 2011 at 2:24 PM, anshu mishra
>> wrote:
>>
>>> two thing i have forgot do;
>>>
>>> that is at every iteration
>>>
>>> rem--;
>>> last = D[i-1];
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
@Ashish: complexity for your solution is O(n*Total seconds)
On Wed, May 25, 2011 at 5:25 PM, Ashish Goel wrote:
> Hi
>
> I was just thinking of a simpler solution
>
> find sum of the time all processes will take, lets call that sum, say for
> 8,1,3,3,8 it is 23
> walk over each process to see if this has been completely executed, if not
> set the out[i]=curTime and reduce the T[i] by 1.(out is the process final
> end time and T is the time process will take if run without halt i.e.
> 8,1,3,3,8)
>
> t=0;
> while (t<=sum)
> {
>
> for (int i=0;i{
> if (T[i]>0) {t++; out[i]=t; T[i]--;}
>}
> }
>
> I must say that this is naive solution
>
> I am not able to understand how interval tree and the code given
> by anshumishra6827 will work. Even if this is right, what was the rationale
> for using segment tree and what is the loop doing by playing with ans, D,
> L..
>
> Best Regards
> Ashish Goel
> "Think positive and find fuel in failure"
> +919985813081
> +919966006652
>
>
> On Wed, May 25, 2011 at 2:24 PM, anshu mishra
> wrote:
>
>> two thing i have forgot do;
>>
>> that is at every iteration
>>
>> rem--;
>> last = D[i-1];
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
Hi
I was just thinking of a simpler solution
find sum of the time all processes will take, lets call that sum, say for
8,1,3,3,8 it is 23
walk over each process to see if this has been completely executed, if not
set the out[i]=curTime and reduce the T[i] by 1.(out is the process final
end time and T is the time process will take if run without halt i.e.
8,1,3,3,8)
t=0;
while (t<=sum)
{
for (int i=0;i0) {t++; out[i]=t; T[i]--;}
}
}
I must say that this is naive solution
I am not able to understand how interval tree and the code given
by anshumishra6827 will work. Even if this is right, what was the rationale
for using segment tree and what is the loop doing by playing with ans, D,
L..
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Wed, May 25, 2011 at 2:24 PM, anshu mishra wrote:
> two thing i have forgot do;
>
> that is at every iteration
>
> rem--;
> last = D[i-1];
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
can a descriptive explaination be provided to this, unfortunately not clear the idea of for loop Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Wed, May 25, 2011 at 4:50 PM, ankit sambyal wrote: > thanks anshu, i m working with segment trees now. Ur algo seems convincing > to me. > nice solution !! > > > Ankit > > > > > On Wed, May 25, 2011 at 1:54 AM, anshu mishra > wrote: > >> two thing i have forgot do; >> >> that is at every iteration >> >> rem--; >> last = D[i-1]; >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
thanks anshu, i m working with segment trees now. Ur algo seems convincing to me. nice solution !! Ankit On Wed, May 25, 2011 at 1:54 AM, anshu mishra wrote: > two thing i have forgot do; > > that is at every iteration > > rem--; > last = D[i-1]; > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
two thing i have forgot do; that is at every iteration rem--; last = D[i-1]; -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
first for every element get the number of element before its index have less
value.
example
L[]= 0 0 1 1 3
D[] = 8 1 3 3 8
IN[] = 0 1 2 3 4
you can use segment tree for this it will give solution in o(nlogn);
after that sort the array and start from 0th index
D[] = {1 3 3 8 8}
IN[] = {1 2 3 0 4}
rem = n;
curtime = 0;
last = 0;
for (i = 0; i < n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
i++;
while (i < n && D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]]; i++;
}
curtime += (D[i] - last) * rem;
}
finally answer will be solution;
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Round Robin Schedulling Problem
Hey guys, I tried to solve this problem https://www.spoj.pl/problems/RRSCHED/I am getting TLE.Does anybdy has any idea of how to solve this problem in an efficient manner ?? Regards, Ankit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
