Avid TV watcher

Problem

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. WAP to find the program and channel number so that the person can spend his max time on TV.

Condition: If he watches a program, he watches it completely.

Example:
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

Solution

Method 1 - Dynamic programming
Answer: This is a clear case of dynamic programming. If you remember problem of longest increasing subsequence, you will be able to see a similarity between this and LIS problem. Lets calculate that if I includes program x in my schedule then how can I spent most of my time on tv till the end of program x. So when I calculate the same for the last program among all the channels, I will be easily able to tell that what will be maximum time, I can spend on tv.

Algorithm: I have a data structure, which represents a program as below:

Class Program{    
    int id;                //unique id to identify a program    
    int cnt;              //This will tell me what max\_time, I can spend on    
                       //tv till end of this program, if I include this program.    
    int start;            // Start time of the program    
    int end;             // End time of the program    
    int channel\_no; // Channel id of the program, skipped in main code    
}

The embedded doc (by Akash Agrawal) below shows the algorithm

Avid tv watcher from Akash Agrawal

If you can’t refer this document, then you can view it here.

Here is a code in java

class Program  implements Comparable <Program>  
{      
 public int id;             //unique id to identify a program    
 public int cnt;            //This will tell me what max\_time, I can spend on    
       //tv till end of this program, if I include this program.    
 public int start;          // Start time of the program    
 public int end;            // End time of the program    
 public int channel\_no;     // Channel id of the program    
     
 public Program(char i, int count, int st, int en)    
 {    
   id = i;    
   cnt = count;    
   start = st;    
   end = en;    
 }    
   
 @Override  
 public int  compareTo(Program b )  {    
  Program a = this;  
  if (a.end == b.end)    
   return 0;    
  else    
  if (a.end < b.end)    
    return -1;    
   else    
   return 1;    
 }    
}  
    
  
    
/\* Test Data   
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:30   
\*/    
    
publci static void main(String\[\] args)    
{    
 /\* say it's the final unsorted array after merging.   
 I will sort it using qsort. We should do a sorted   
 merge from individual k channel arrays that will take   
 O(nlogk) time where n is total number of programs.\*/    
  
 Program\[\] programs = new Program\[6\];  
 programs={    
  Program(1,0,800,850),    
  Program(2,0,900,1000),    
  Program(3,0,1050,1150),    
  Program(4,0,825,925),    
  Program(5,0,950,1025),    
  Program(6,0,1075,1150)    
 };    
 int i, max, j, n;    
    
 // Printing Just for Debuging    
 for (i=0;i<6;i++)    
  System.out.println( programs\[i\].id );    
    
 /\*Sort the array. We should do a sorted merge from individual   
 k channel-arrays that will take O(nlogk) time where n is   
 total number of programs. \*/    
 Arrays.sort(programs);  
    
 // Printing Just for Debuging    
 for (i=0;i<6;i++)    
 System.out.println( programs\[i\].id );    
    
 n = sizeof(programs)/sizeof(prog);    
    
 for (i=0; i< n; i++)    
 {    
  max = 0;    
  j = 0;    
  while (programs\[i\].start > programs\[j\].end )    
  {    
   if (max < programs\[j\].cnt)    
   {    
    max = programs\[j\].cnt;    
   }    
   j++;        
  }    
  programs\[i\].cnt = max + programs\[i\].end - programs\[i\].start;    
 }    
    
 //Get the maximum count value    
 int res = 0;    
 for (i=0; i< n; i++)    
 {    
  if (res < programs\[i\].cnt)    
   res = programs\[i\].cnt;        
 }    
     
 System.out.println( "result =" + res );    
 return 0;    
}

Efficiency:
This has a few steps:

Merge sort individual k channel arrays: O(nlogk) where n is total number of programs.
Find count for each program. For finding count for each program, in worst case we need to traverse all the programs. So O(n). For n programs total complexity: O(n^2).
Find maximum cnt in programs array: O(n)

So total complexity will be O(nlogk) + O(n^2) + O(n) = O(n^2)

Update: Another version of this problem can be to find maximum number of programs that person can watch.

You can also see which program he will watch by saving predecessor in another array as we do in LIS.

References - http://tech-queries.blogspot.in/2011/03/avid-tv-watcher.html

Thanks

See also