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.