当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3814:Museum Guards

题目描述
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:

Each guard works during the same time intervals every day.
Each guard works within his/her time windows of availability, which s/he specifies.
Each guard works at most the amount of time s/he is able, which s/he also specifies.
The guards can only shift (start or stop working) on half hour boundaries. (e.g. 04:00 or 04:30, but not 04:15).
The guards are only scheduled for shifts if they are available to work at all times during those shifts. (e.g. if a guard's window of availability opens at 03:05, they cannot be scheduled at 03:00.)
The minimum number of guards on duty at any time during the day is maximized. This improves security of the museum.

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

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-3814

最后修改于 2020-10-29T07:12:40+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000 65536