2014 Mock CCC by Alex and Timothy
Problem J4: Selecting Shifts
Alice figured out where Bob works, and has obtained a job there so she can secretly admire him at work. Because she is new, the position is only part-time, and she is always called in to shifts by her boss. Whenever this happens, she is offered various shifts to pick from, starting and ending at different times of the day. Alice knows that Bob works from T1 to T2 on days that she's called in.
Alice's employer has given her a list of the shifts that she can choose from in order of decreasing pay. Given this list, Alice would like to know which one would result in the longest period of time that both of them are simultaneously on the job. If multiple shifts yield the same time spent with Bob, she would like to know the highest paying out of those (i.e. the one that appears earliest in the list).
Input Format
Line 1 contains T1 and T2, the time that Bob starts and ends his shift.
Line 2 contains the integer N (1 ≤ N ≤ 100), the number of shifts that Alice is being offered.
The next N lines each contain two times — the start and end times of that shift. The shifts are ordered by decreasing pay.
Times in the input will be in the 7 character long format as depicted in the sample input below, and will all describe times within the same 24 hour day (between 12:00AM and 11:59PM, inclusive). Every shift described will have the start time strictly before the end time.
Output Format
The start and end time of the shift that Alice should pick to maximize the time she gets to spend on the job with Bob. If there are multiple answers, pick the one that is higher up on the list. If none of the shifts overlap with Bob's shift, output "Call in a sick day." (without quotes), since Alice has no interest in wasting her time at work when Bob is not there.
Sample Input
10:30AM 07:00PM 4 05:30AM 10:00AM 11:00AM 08:15PM 01:45PM 05:00PM 08:00PM 11:00PM
Sample Output
11:00AM 08:15PM
Explanation
Bob works from 10:30AM to 7:00PM. If Alice picks the shift from 1:45PM to 5:00PM, she will spend 3 hours and 15 minutes on the job with Bob. If Alice picks the shift from 11:00AM to 8:15PM, she will spend 8 hours on the job with Bob (from 11:00AM to 7:00PM, when Bob gets off). The shift from 5:30AM to 10:00AM ends before Bob even goes in to work, and the shift at 8:00PM starts after Bob has already left.
All Submissions
Best Solutions
Point Value: 7 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 27, 2014
Author: Alex
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
(probably) make sure your formating is right and make sure your output is the exact same as the sample