Problem G
Office Hours 2
It’s the start of a very busy semester, and your professor wants to determine when to schedule office hours so that they can be attended by as many students as possible. They have schedules for every student, but there are a lot of students! Can you write an algorithm to determine which two hours in the week will maximize the number of students who can attend at least one office hour?
Input
The first line is an integer $2 \leq N \leq 10\, 000$, the number of lines that specify the student schedules.
The following $N$ lines specify the availability of a single student on a single day. Each line contains a series of space-separated fields. The first field consists of between $1$ and $10$ alphabetical characters, specifying the student’s name. The second field is the day of the week for which the student is reporting availability (e.g. “Monday”), including weekends. The third field is an integer $1 \leq P \leq 24$, the number of unique, non-overlapping time ranges for which the student has reported availability. The final $P$ fields on the line are time ranges, in the format x-y, where $x < y$ and $x$ and $y$ are both integers between $0$ and $24$, inclusive, specifying the hour that marks the beginning and end of their availability, respectively.
Note that the combination of student name and day is unique. That is, a student will not report their availability for the same day on multiple lines.
Note also that the input will be such that there is a unique combination of two hours for which the maximum number of students are available.
Output
Two lines specifying the two days and times that maximize the number of students that can attend at least one office hour. The first line should represent a time occurring earlier in the week than the second line, assuming that Sunday at hour $0$ represents the beginning of the week.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 Emily Monday 2 9-13 14-15 John Monday 1 12-14 Sarah Monday 1 15-16 |
Monday 12 Monday 15 |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 Juan Tuesday 2 1-7 15-17 Juan Thursday 3 8-10 12-14 16-18 Hannah Monday 2 9-12 14-17 Bob Monday 1 12-14 Bob Thursday 2 5-6 14-17 Darnell Monday 1 16-24 Katy Sunday 1 12-13 |
Monday 16 Thursday 16 |
