U can always have a trackback array as we do in LIS. Regards, Akash Agrawal http://tech-queries.blogspot.com/
On Fri, Mar 4, 2011 at 5:48 PM, Vipin Agrawal <[email protected]>wrote: > 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 <[email protected]> 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 <[email protected] > >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 < > [email protected]>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 < > [email protected]>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 <[email protected] > >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 < > [email protected]>wrote: > > > > >>>>> or provide some link > > > > >>>>> On Mon, Jan 31, 2011 at 10:44 PM, snehal jain < > [email protected]>wrote: > > > > >>>>>> @ juver++ > > > > >>>>>> can you please share your approach > > > > >>>>>> On Mon, Jan 31, 2011 at 8:43 PM, Divya Jain < > [email protected] > > >>>>>> > 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 <[email protected]> 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 < > > >>>>>>>> [email protected]> 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 > [email protected]. > > >>>>>>>>> To unsubscribe from this group, send email to > > >>>>>>>>> [email protected]. > > >>>>>>>>> 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 [email protected] > . > > >>>>>>>> To unsubscribe from this group, send email to > > >>>>>>>> [email protected]. > > >>>>>>>> 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 [email protected]. > > >>>>>>> To unsubscribe from this group, send email to > > >>>>>>> [email protected]. > > >>>>>>> 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 [email protected]. > > >>>>> To unsubscribe from this group, send email to > > >>>>> [email protected]. > > >>>>> 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 [email protected]. > > >>>> To unsubscribe from this group, send email to > > >>>> [email protected]. > > >>>> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
