Problem Statement |
| |
A carrier boat is initially on the left bank of a river. Cargo becomes available at either side of the river at various times. Each cargo unit must be loaded onto the boat, carried across the river to the opposite side, and unloaded. It takes T units of time to cross the river, and the boat can carry at most units units of cargo at a time. Loading and unloading cargo is instantaneous. The boat can wait at either side of the river and depart at any time. After all the cargo has been transported, it does not matter which side of the river the boat ends up at. Each element of cargo represents one or more cargo units, ordered in non-decreasing order by the time at which they become available.
The waiting time of a cargo unit is the difference between the time at which it becomes available and the time at which it is loaded onto the boat. The time spent by a cargo unit while it's inside the boat does not count toward its waiting time. For example, if a cargo unit becomes available at time 0 and is loaded onto the boat at time 5, its waiting time is 5 regardless of how much longer the boat waits before departing. Determine a schedule for the boat that minimizes the sum of all the waiting times. Return this minimal sum.
You are given a String[] cargo where each element is formatted as "units time bank" (quotes for clarity only).
- units is the number of cargo units that become available.
- time is the time at which they become available.
- bank is the side of the river at which they become available - either "left" or "right" (quotes for clarity only).
Even though multiple units of cargo may become available at the same time, they do not need to remain together or be loaded onto the boat at the same time. |
| |
Definition |
| | | Class: | RiverCrossing | | Method: | minimalWait | | Parameters: | String[], int, int | | Returns: | int | | Method signature: | int minimalWait(String[] cargo, int units, int T) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | cargo will contain between 1 and 50 elements, inclusive. |
| - | units will be between 1 and 50, inclusive. |
| - | T will be between 1 and 100, inclusive. |
| - | Each element of cargo will be formatted as "units time bank" (quotes for clarity only). |
| - | Elements of cargo will be ordered in non-decreasing order of time. |
| - | In each element of cargo, units will be an integer between 1 and 50, inclusive, with no leading zeroes. |
| - | In each element of cargo, time will be an integer between 1 and 100, inclusive, with no leading zeroes. |
| - | In each element of cargo, bank will be either "left" or "right" (quotes for clarity only). |
| - | The total units of cargo to be transported will be less than or equal to 200. |
| |
Examples |
| 0) | |
| | | Returns: 22 | The boat moves as follows:
- Time 0: The boat departs from the left bank.
- Time 3: The boat arrives at the right bank, loads 3 units of cargo, and departs. The total waiting time for those 3 units is 3*(3-1)=6.
- Time 6: The boat arrives at the left bank, unloads its cargo, and departs.
- Time 9: The boat arrives at the right bank, loads the remaining 2 units of cargo, and departs. The total waiting time for those 2 units is 2*(9-1)=16.
- Time 12: The boat arrives at the left bank and unloads its cargo. The total waiting time was 6+16=22.
|
|
|
| 1) | |
| | |
| 2) | |
| | {"1 1 left", "1 1 right", "2 4 left"} | 3 | 2 |
| Returns: 4 | |
|
| 3) | |
| | {"20 1 left", "20 2 left", "20 3 left", "20 4 left", "20 5 left",
"20 6 left", "20 7 left", "20 8 left", "20 9 left", "20 10 left"} | 1 | 100 |
| Returns: 3979100 | | You always go from right to left with an empty boat. |
|
|
| 4) | |
| | {"20 1 right", "20 2 left", "20 3 right", "20 4 left", "20 5 right",
"20 6 left", "20 7 right", "20 8 left", "20 9 right", "20 10 left"} | 1 | 100 |
| Returns: 1989300 | | Coming back with a filled boat reduces the waiting time. |
|
|
| 5) | |
| | {"4 15 left", "10 24 left", "3 35 left", "10 47 right",
"4 51 right", "10 56 right", "9 65 left"} | 12 | 34 |
| Returns: 1660 | |
|