TopCoder problem "Conference" used in TCO05 Semi 3 (Division I Level Two)



Problem Statement

    Our department is sending n faculty members to an academic conference and we are determined to cover as many meetings as possible. We have a list of all the meetings, with their start and end times. All the meetings are in adjacent rooms so no time is required to travel from one meeting to another. This means that if the end time of one meeting is the same as the start time of another meeting, a single person could cover both meetings from start to end.

Each element of the String[] meetings gives the start and end time of a meeting, separated by a single space. Each time is given in the form hh:mm and represents a time between 08:00 in the morning and 08:00 in the evening inclusive.

Create a class Conference that contains a method coverage that is given n, the number of faculty sent to the conference, and the String[] meetings listing the times of all the meetings. The method returns the most meetings that we can cover by having at least one faculty member at the meeting from start to end.

 

Definition

    
Class:Conference
Method:coverage
Parameters:int, String[]
Returns:int
Method signature:int coverage(int n, String[] meetings)
(be sure your method is public)
    
 

Constraints

-n will be between 1 and 10, inclusive.
-meetings will contain between 1 and 50 elements, inclusive.
-Each element of meetings will contain 11 characters in the form "hh:mm hh:mm"
-Each hh:mm will represent a time between 8 am and 8 pm inclusive.
-Each mm will be between 00 and 59, inclusive.
-In each element of meetings the second time will be strictly later than the first.
 

Examples

0)
    
3
{"08:00 08:00","08:00 08:00","08:00 08:00",
 "08:00 08:00","08:00 08:00"}
Returns: 3
All these meetings last all day long. Nobody can cover more than one.
1)
    
2
{"09:00 08:00","08:00 12:00","12:00 08:00",
 "08:00 08:00","08:00 08:00"}
Returns: 3
One person can cover the 8-12 meeting and the 12-8 meeting. The other person can cover one of the all-day meetings.
2)
    
1
{"08:00 01:00","08:25 12:50","12:00 12:30",
 "12:30 08:00","08:00 08:00"}
Returns: 2

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8093&pm=3476

Writer:

dgoodman

Testers:

PabloGilberto , lbackstrom , vorthys , Olexiy

Problem categories:

Greedy, String Parsing