|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|5 초||128 MB||1||1||1||100.000%|
A museum has hired some guards and is trying to build a schedule for them. The museum would like to build a 24-hour schedule for the guards, such that:
Write a program to help the museum staff determine the maximum number of guards that they can maintain at all times throughout a 24-hour day, given the constraints of the guards‟ availability. You may assume that guard exchanges are instantaneous. That is, if 2 guards leave and 2 other guards arrive at the same time, the museum is guarded by 2 guards through this exchange.
There will be multiple test cases. Each test case begins with a line containing a single integer N (1 ≤ N ≤ 50), the number of guards available. There will then be N blocks of data, one for each guard.
Each block provides the preferences of one guard. A block begins with two integers, K (1 ≤ K ≤ 50) and M (1 ≤ M ≤ 1440), in that order; K is the number of time intervals specifying when the guard is available for work, and M is the maximum number of minutes s/he is able to work each day. The next K lines each contains the starting and ending time, in that order, of a time interval where the guard is available, separated by whitespace. These time intervals may overlap. The union of all K time intervals provides the complete set of times at which the guard is available.
A starting or ending time is formatted as HH:MM (00 ≤ HH ≤ 23, 00 ≤ MM ≤ 59). Midnight is represented by 00:00. When the ending time is smaller than the starting time, it means the guard is available for working past midnight. For example, the interval “23:00 03:00” means the guard is available from 11pm at night to 3am in the morning. If the starting and ending times are equal, then the guard is available for work during any time intervals throughout the day. The last test case is followed by a line with a single 0.
For each test case, output a single integer, representing the minimum number of guards on duty at any given time during the day, using a schedule that maximizes this value. That is, output the largest integer k, such that there is a schedule where at any given moment, there are k guards on duty at the museum, assuming instantaneous exchanges specified above. Do not print any blank lines between answers.
3 1 540 00:00 00:00 3 480 08:00 10:00 09:00 12:00 13:00 19:00 1 420 17:00 00:00 5 1 720 18:00 12:00 1 1080 00:00 23:00 1 1080 00:00 20:00 1 1050 06:00 00:00 1 360 18:00 00:00 3 1 1440 00:00 00:00 1 720 00:00 12:15 1 720 12:05 00:15 0
1 2 1