PROBLEM STATEMENT
An airline freight sorting hub unloads freight into containers. Every time a
plane arrives, one container is used to unload the plane. After the plane has
departed, the container into which the freight has been unloaded may become
unavailable for several hours. After that, the container becomes available
again. Given schedules for all planes arriving at the freight hub and the delay
between plane's departure and the time when its container becomes available,
determine the smallest number of containers required to service all planes on
the schedule.
DEFINITION
Class name: Freight
Method name: containers
Parameters: String[], int
Return type: int
Method signature (be sure your method is public): int containers(String[]
schedule, int delay);
Each string in the schedule has 24 characters, and represents an hour-by-hour
schedule of one plane. Each position in the string corresponds to an hour of
the day; '1' (one) and '0' (zero) are the only characters allowed in the
strings. When position X in the string contains '1', the plane is at the hub at
the hour X; when the character is '0', the plane is not at the hub at that
hour. The schedule for each plane repeats itself every 24 hours (in a sense, it
is circular). You need to take this into account when figuring out planes'
arrivals and departures: for example, "100000000000000000000001" shows a single
arrival at 23:00 (11:00 PM), and a single departure at 1:00 AM. Each plane has
to arrive and depart at least once; in other words, "111111111111111111111111"
and "000000000000000000000000" are not valid schedules.
delay represents the number of hours the container is unavailable after the
departure of its corresponding plane.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- schedule contains 1 to 50 elements, inclusive,
- Elements of schedule are exactly 24 characters in length
- Elements of schedule do not contain characters other than '0' (zero) and '1'
(one),
- Each element of schedule contains at least one '0' (zero) character,
- Each element of schedule contains at least one '1' (one) character,
- The value of delay is between 0 and 23, inclusive.
NOTE
Reuse of containers follows the same 24-hour cycle as the schedule of the
planes. For example, if a plane arrives at 22:00 (10:00 PM) and departs at
23:00 (11:00 PM) and the delay is 2, the corresponding container becomes
available at 1:00 AM.
EXAMPLES
1. Consider the following schedule:
{ "110000000000001000000001", // plane #1
"110000000001110000000000", // plane #2
"000111110000000111100000"} // plane #3
If the delay is 0 or 1, your method should return 2.
Consider the example where delay = 1 :
- two planes (#1 and #2) depart at 2:00, making two containers available at 3:00;
- one of these containers is used for plane #3 at 3:00;
- after the plane #3's departure at 8:00, the container becomes available at
9:00;
- at 11:00, one of the two free containers becomes used again for plane #2;
- at 14:00, the second container becomes used for plane #1; in the meantime,
plane #2 departs;
- at 15:00, plane #3 arrives, and plane #1 departs; at the same time, the
container from the previously departed plane #2 becomes available, so it is
ready for use by plane #3;
- at 16:00, container used by plane #1 frees up;
- at 19:00, plane #3 departs;
- at 20:00, container used by plane #3 frees up;
- at 23:00, plane #1 arrives, requiring one of the two free containers;
- at 0:00, plane #2 arrives, requiring the second of the two free containers.
This completes the circle - since we managed to service all planes on the
schedule with only two containers, your method should return 2.
If the delay is 2 through 7, inclusive, your method should return 3;
If the delay is 8 through 10, inclusive, your method should return 4;
If the delay is 11 through 13, inclusive, your method should return 5;
If the delay is 14 through 19, inclusive, your method should return 6;
If the delay is 20 through 22, inclusive, your method should return 7;
If the delay is 23, your method should return 8.
2. If the schedule is
{ "000100000000000000000001", // plane #1
"010000000000000000000000"} // plane #2
and the delay is 0 or 1, your method should return 1;
if the delay is 2 or 3, your method should return 2;
if the delay is 4 through 23, inclusive, your method should return 3.