Avid TV watcher | PROGRAMMING INTERVIEWS

Avid TV watcher | PROGRAMMING INTERVIEWS
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
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
qsort(programs, 6, sizeof(prog), comp) ;
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;
}
http://k2code.blogspot.com/2014/03/avid-tv-watcher.html

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; 

 } 

}

 /*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);   

 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; 

} 

http://code.qtuba.com/article-10066.html
今年暑假不AC？”“是的。”“那你干什么呢？”“看世界杯呀，笨蛋！”“@#$%^&*%...”确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看一些其它的节目，比如新闻联播（永远不要忘记关心国家大事）、非常6+7、超级女生，以及王小丫的《欢乐辞典》等等，假设你已经知道了所有你爱慕看的电视节目的转播时间表，你会合理安排吗？（目标是能看尽量多的完整节目）

 for(int i=0;i<n;i++)
 {
  cin>>buf[i].stime>>buf[i].etime;
 }
 sort(buf,buf+n);
 int ctime=0,ans=0;
 for(int i=0;i<n;i++)
 {
  if(ctime<=buf[i].stime)
  {
   ctime=buf[i].etime;
   ans++;
  }
 }
 cout<<ans<<endl;

X.  http://www.acmerblog.com/jiudu-1434-2383.html

06	struct Node {

07

int s, e;

08	} nodes[101];

09

10	bool cmp(const Node & n1, const Node & n2) {

11	return n1.e < n2.e;

12

}

13	int opt[101];

14	int main() {

15

16	while(cin >> n, n) {

17	for(int i=0; i<n; i++) {

18	cin >> nodes[i].s >> nodes[i].e;

19	opt[i] = 0;

20

}

21	sort(nodes, nodes+n, cmp);

22	opt[0] = 1;

23	for(int i=1; i<n; i++) {

24	for(int j=i-1; j>=0; j--) {

25	if(nodes[i].s >= nodes[j].e) {

26	opt[i] = opt[j]+1;

27

break;

28

}

29

}

30	if(opt[i] < opt[i-1]) {

31	opt[i] = opt[i-1];

32	nodes[i].e = nodes[i-1].e;

33

}

34

}

35	cout << opt[n-1] << endl;

36

}

37

38

return 0;

39

}

Read full article from Avid TV watcher | PROGRAMMING INTERVIEWS