Friday, October 21, 2011

Maximising the duration

There is a TV avid person, who wants to spend his maximum time on TV. There are N channels that telecast programs of different length at different timings. Find the program and channel number so that the person can spend his max time on TV. If the person watches a program, he watches it completely.

For e.g
Channel1:
prg1: 8:00 am - 9:00am
prg2: 9:30 am - 12:00 am

Channel2:
prg1: 8:15 am - 9:30am
prg2: 9:30 am - 11:45 am

In this case, between 8:00 AM to 12:00 noon, the answer is:

ch2/prg1 + ch1/prg2

Approach:

Sort the programs with the end times. And then apply the greedy algorithm to find the maximum duration.