Solution is good, but its says only Max time that he can spend. How would he know that which program he should watch for Maximum utilization ?
On Mar 4, 4:38 pm, Akash Agrawal <akash.agrawa...@gmail.com> wrote: > http://tech-queries.blogspot.com/2011/03/avid-tv-watcher.html > > Regards, > Akash Agrawalhttp://tech-queries.blogspot.com/ > > On Fri, Mar 4, 2011 at 2:25 PM, Akash Agrawal > <akash.agrawa...@gmail.com>wrote: > > > Example: > > > Channel 1: > > > Program id > > > P1 > > > P2 > > > P3 > > > Start time > > > 8:00 > > > 9:00 > > > 10:30 > > > End time > > > 8:30 > > > 10:00 > > > 11:30 > > > Channel 2: > > > Program id > > > P4 > > > P5 > > > P6 > > > Start time > > > 8:15 > > > 9:30 > > > 10:45 > > > End time > > > 9:15 > > > 10:15 > > > 11:15 > > > Sort all programs based on their end time: > > > Cnt > > > 0 > > > 0 > > > 0 > > > 0 > > > 0 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 1st Iteration: > > > Cnt > > > 00:30 > > > 0 > > > 0 > > > 0 > > > 0 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 2nd Iteration: > > > Cnt > > > 00:30 > > > 01:00 > > > 0 > > > 0 > > > 0 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 3rd Iteration: > > > Cnt > > > 00:30 > > > 01:00 > > > 01:30 > > > 0 > > > 0 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 4th Iteration: > > > Cnt > > > 00:30 > > > 01:00 > > > 01:30 > > > 01:45 > > > 0 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 5th Iteration: > > > Cnt > > > 00:30 > > > 01:00 > > > 01:30 > > > 01:45 > > > 02:30 > > > 0 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > 6th Iteration: > > > Cnt > > > 00:30 > > > 01:00 > > > 01:30 > > > 01:45 > > > 02:30 > > > 02:45 > > > Pr id > > > P1 > > > P4 > > > P2 > > > P5 > > > P6 > > > P3 > > > St time > > > 8:00 > > > 8:15 > > > 9:00 > > > 9:30 > > > 10:45 > > > 10:30 > > > End time > > > 8:30 > > > 9:15 > > > 10:00 > > > 10:15 > > > 11:30 > > > 11:30 > > > Answer will be 2:45 hrs as this is the biggest value in Cnt. > > > Regards, > > Akash Agrawal > >http://tech-queries.blogspot.com/ > > > On Fri, Mar 4, 2011 at 2:17 PM, Akash Agrawal > > <akash.agrawa...@gmail.com>wrote: > > >> Seems, it didn't preserve indentation. attached file. > > >> Regards, > >> Akash Agrawal > >>http://tech-queries.blogspot.com/ > > >> On Fri, Mar 4, 2011 at 2:16 PM, Akash Agrawal > >> <akash.agrawa...@gmail.com>wrote: > > >>> First try urself with thinking longest common subsequence if u r still > >>> not able to see below algo. I will write a blog post soon for the same. > > >>> Funda is to see what is the max time I can spend on TV if I watch program > >>> X. > > >>> 1. Merge all the programs of diff channels in sorted order of their > >>> end-time in prog[] array. (need O(nlogk)) > > >>> 2. n ← length(prog) - 1 > > >>> 3. for i ← 1 to n > > >>> a. do prog[i].cnt ← 0 > > >>> b. max ← 0 > > >>> c. j ← 0 > > >>> d. while prog[j].end < prog[i].start > > >>> i. if max < > >>> prog[j].cnt > > >>> 1. do max ← proj[j].cnt > > >>> ii. j ← j + 1 > > >>> e. do prog[i].cnt ← max + prog[i].end – prog[i].start > > >>> 4. do res ← 0 > > >>> 5. for i ← 1 to n > > >>> a. if res < prog[i].cnt > > >>> i. do res ←prog[i].cnt > > >>> 6. return res > > >>> PS: Hope it saved indentation. > > >>> Regards, > >>> Akash Agrawal > >>>http://tech-queries.blogspot.com/ > > >>> On Tue, Feb 1, 2011 at 2:46 PM, Vikas Kumar <dev.vika...@gmail.com>wrote: > > >>>> @Snehal > > >>>> just a hint: there is no need of that channel 1 & channel 2. > > >>>> just treat each program as independent program. > > >>>> On Mon, Jan 31, 2011 at 10:44 PM, snehal jain > >>>> <learner....@gmail.com>wrote: > > >>>>> or provide some link > > >>>>> On Mon, Jan 31, 2011 at 10:44 PM, snehal jain > >>>>> <learner....@gmail.com>wrote: > > >>>>>> @ juver++ > > >>>>>> can you please share your approach > > >>>>>> On Mon, Jan 31, 2011 at 8:43 PM, Divya Jain <sweetdivya....@gmail.com > >>>>>> > wrote: > > >>>>>>> @ above > > >>>>>>> ur code fails for following example > >>>>>>> channel 1 : prog1 8:00-9:00, prog 2 9:00-10:00 > >>>>>>> channel 2 : prog1 8:15-10:00 > > >>>>>>> your code returns 8:15- 10 > >>>>>>> and the answer should be channel1/prog1 + channel1/prog2 > > >>>>>>> On 21 January 2011 12:54, Anand <anandut2...@gmail.com> wrote: > > >>>>>>>> Sort all program with their starting time. > > >>>>>>>> Appy the below pseudo code to find max number of programs he can > >>>>>>>> watch. > > >>>>>>>> for(i=i;i<len;i++) > >>>>>>>> { > >>>>>>>> /*Check for overlap */ > >>>>>>>> if(p[i].start > p[i-1].end) > >>>>>>>> { > >>>>>>>> end = i; > >>>>>>>> } > >>>>>>>> else > >>>>>>>> { > >>>>>>>> /*Index of the first program to be watch*/ > >>>>>>>> if((p[i-1].end - p[i-1].start) < (p[i].end - p[i].start)) > >>>>>>>> { > >>>>>>>> start = i; > >>>>>>>> } > >>>>>>>> } > > >>>>>>>> } > >>>>>>>> return end - start; > > >>>>>>>> On Thu, Jan 20, 2011 at 10:11 PM, snehal jain < > >>>>>>>> learner....@gmail.com> wrote: > > >>>>>>>>> There is a TV avid person. HE wants to spend his max time on TV. > >>>>>>>>> There > >>>>>>>>> are N channels with different program of different length and diff > >>>>>>>>> times. WAP so that the person cam spend his max time watching TV. > >>>>>>>>> Precondition: If that person watches a program, he watches it > >>>>>>>>> completely. > > >>>>>>>>> Ex: > >>>>>>>>> Channel1: prog1 – 8:00- 8:30 > >>>>>>>>> prog2: 9:00 – 10:00 > >>>>>>>>> prog3: 10:15 – 12:00 > > >>>>>>>>> channel2: prg1 – 8:15 – 10:00 > >>>>>>>>> prg2: 10:30 – 12:00 > > >>>>>>>>> So in this case max time will be if he watches: > > >>>>>>>>> ch2/prg1 + ch1/prg3 > > >>>>>>>>> -- > >>>>>>>>> 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. > > >>>> -- > >>>> 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.
