Re: [algogeeks] Re: Scheduling
Will this work ? Order by choosing the last element of the permutation first. initially Calculate T = Total time of all tasks and calculate for all i, (T-Ti)*Ci and choose the task with min among them as last. To find the next last element , re-calculate T = T-Ti(i being the element chosen in prev step) and proceed with the same steps as mentioned above. On Tue, Jun 7, 2011 at 6:43 PM, ross jagadish1...@gmail.com wrote: @Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.com wrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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] Re: Scheduling
can you give the problem link ? On Thu, Jun 9, 2011 at 12:38 PM, Algoose chase harishp...@gmail.com wrote: Will this work ? Order by choosing the last element of the permutation first. initially Calculate T = Total time of all tasks and calculate for all i, (T-Ti)*Ci and choose the task with min among them as last. To find the next last element , re-calculate T = T-Ti(i being the element chosen in prev step) and proceed with the same steps as mentioned above. On Tue, Jun 7, 2011 at 6:43 PM, ross jagadish1...@gmail.com wrote: @Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.com wrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- Regards, Arpit Sood -- 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] Re: Scheduling
ya aanchal, kaun si problem hai? On Sun, Jun 12, 2011 at 1:41 AM, Arpit Sood soodfi...@gmail.com wrote: can you give the problem link ? On Thu, Jun 9, 2011 at 12:38 PM, Algoose chase harishp...@gmail.comwrote: Will this work ? Order by choosing the last element of the permutation first. initially Calculate T = Total time of all tasks and calculate for all i, (T-Ti)*Ci and choose the task with min among them as last. To find the next last element , re-calculate T = T-Ti(i being the element chosen in prev step) and proceed with the same steps as mentioned above. On Tue, Jun 7, 2011 at 6:43 PM, ross jagadish1...@gmail.com wrote: @Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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. -- Regards, Arpit Sood -- 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.
[algogeeks] Re: Scheduling dp problem - MSFT interview
sort the jobs increasingly according to ratio: duration/penalty. It is easy to prove it's optimal for two jobs. Then you generalize the proof for n jobs easily because you can swap two consecutive jobs i,j that have duration(i)/penalty(i)duration(j)/ penalty(j) to decrease the total penalty of the schedule (same reasoning as for two jobs + a constant for the ones before and after that remain unchanged). On May 30, 7:00 pm, ross jagadish1...@gmail.com wrote: You are given a sequence of jobs. The no. of days which each job takes to complete is also provided. You are also given the penalty amount to be paid per day each day a job left done. Give an optimal ordering among jobs to minimize penalty. There are no concurrent jobs. eg: Jobs: J1 J2 J3 no. of days to complete: 1 10 4 Penalty incurred each day 1000 30 40 the job is pending output: Schedule is J1 J3 J2 hence, J1 goes for 1st day. J3 for subsequent 4 days. J2 for the next 10 days. Penalty incurred = (delay for job i ) * (penalty per day of job i) = = (0)(1000) + (1)(40) + 5(30) = 190 -- 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] Re: Scheduling dp problem - MSFT interview
Yes, pshaus is absolutely right. I have just confirmed it by exchange arguments. Just schedule the one first having (duration/panelty) ratio lesser. On Wed, Jun 8, 2011 at 12:01 AM, pschaus psch...@gmail.com wrote: sort the jobs increasingly according to ratio: duration/penalty. It is easy to prove it's optimal for two jobs. Then you generalize the proof for n jobs easily because you can swap two consecutive jobs i,j that have duration(i)/penalty(i)duration(j)/ penalty(j) to decrease the total penalty of the schedule (same reasoning as for two jobs + a constant for the ones before and after that remain unchanged). On May 30, 7:00 pm, ross jagadish1...@gmail.com wrote: You are given a sequence of jobs. The no. of days which each job takes to complete is also provided. You are also given the penalty amount to be paid per day each day a job left done. Give an optimal ordering among jobs to minimize penalty. There are no concurrent jobs. eg: Jobs: J1 J2 J3 no. of days to complete: 1 10 4 Penalty incurred each day1000 30 40 the job is pending output: Schedule is J1 J3 J2 hence, J1 goes for 1st day. J3 for subsequent 4 days. J2 for the next 10 days. Penalty incurred = (delay for job i ) * (penalty per day of job i) = = (0)(1000) + (1)(40) + 5(30) = 190 -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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] Re: Scheduling
@Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.comwrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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.
