TopCoder problem "TVWatching" used in SRM 250 (Division I Level Two)



Problem Statement

    

I really love watching television. If it were possible, I would watch for 24 hours per day! I'm particularly fond of programs that are broadcast at the same time every day (such as the news, sports and series). Going through the TV guide I selected all the programs that are worth watching.

Each element of programs describes a TV program I'd like to watch. An element is formatted as follows: "begintime - endtime" (quotes for clarity), where begintime and endtime are times in 12 hour notation. A valid time in 12 hour notation looks like "hh:mmXX", where hh contains exactly two digits and 01<=hh<=12, mm contains exactly two digits and 00<=mm<=59, and XX is either AM or PM. Programs with a later begintime than endtime wrap around the clock to the next day. If begintime and endtime are equal, the program lasts for 24 hours.

I don't want to see parts of TV programs; I either want to see the whole program or none of it. What is the maximum number of minutes that I can spend per day watching my favorite programs?

 

Definition

    
Class:TVWatching
Method:mostMinutes
Parameters:String[]
Returns:int
Method signature:int mostMinutes(String[] programs)
(be sure your method is public)
    
 

Constraints

-programs has between 0 and 50 elements, inclusive.
-Each element of programs is formatted as described in the problem statement.
 

Examples

0)
    
{"09:00AM - 12:00PM", "02:00PM - 07:00PM", "09:00PM - 02:00AM"}
Returns: 780
Since the three programs don't overlap, you can watch each of them.
1)
    
{"01:15PM - 11:20PM", "08:00AM - 04:13PM", "03:12PM - 12:06AM", "02:00PM - 02:01PM" }
Returns: 605
Watch the first program. The others have some overlap with it.
2)
    
{"12:34PM - 12:34PM"}
Returns: 1440
Same times indicate a 24 hour TV show.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4571

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7225&pm=4571

Writer:

Jan_Kuipers

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming