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.
