Connection Status:
Competition Arena > Conference

Conference

TCO05 Semi 3 · 2005-08-16 · by dgoodman

TCO05 Semi 3 · 2005-08-16 · by dgoodman · Greedy, String Parsing
Class Name: Conference
Return Type: int
Method Name: coverage
Arg Types: (int, vector<string>)
Problem Statement

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.

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
3)
10
{"08:00 08:00","08:00 08:00","08:00 08:00",
 "08:00 08:00","08:00 08:00"}
Returns: 5
4)
2
{"08:00 01:00","09:00 02:00","10:00 03:00",
 "11:00 04:00","12:00 05:00","01:00 06:00"}
Returns: 3

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Conference with a public method int coverage(int n, vector<string> meetings) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous