Problem Statement |
| | Every morning, you drive distance kilometers down a curvy highway to work. Over time, you've noticed some possible shortcuts along the way. For each shortcut, you've recorded where along the highway it starts, where it rejoins the highway, and how long it is. The i-th elements of cutStart, cutEnd, and cutLength describe these three properties, respectively, for the i-th shortcut. The highway and all shortcuts are one way only. This means that you must not overshoot your destination, and you cannot go backwards to take advantage of a shortcut that begins earlier on the road. Figure out the shortest route you can take using any valid combination of shortcuts, and return its length.
|
| |
Definition |
| | | Class: | CommutePlan | | Method: | shortestRoute | | Parameters: | int, int[], int[], int[] | | Returns: | int | | Method signature: | int shortestRoute(int distance, int[] cutStart, int[] cutEnd, int[] cutLength) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | distance will be between 1 and 1000, inclusive. |
| - | cutStart, cutEnd, and cutLength will each contain between 0 and 12 elements, inclusive. |
| - | cutStart, cutEnd, and cutLength will each contain the same number of elements. |
| - | Each element of cutStart, cutEnd, and cutLength will be between 0 and 1000, inclusive. |
| - | Each element of cutStart will be less than the corresponding element of cutEnd. |
| |
Examples |
| 0) | |
| | | Returns: 80 | | The first shortcut saves us 10 kilometers (as we get from 10 to 60, but only drive 40 kilometers). However, taking the first shortcut means we can't use the second one (which would save 20 kilometers). It's best to skip the first and use the second. |
|
|
| 1) | |
| | | Returns: 1000 | | We're in for a long drive with no shortcuts. |
|
|
| 2) | |
| | 150 | {0,0,50,100,110} | {50,50,100,151,140} | {10,20,10,10,90} |
| Returns: 70 | | Our best strategy is to use the shortcuts at indexes 0 and 2. This gets us to kilometer 100 in only 20 kilometers of driving. We can't use the shortcut at index 3 because it overshoots the destination. We don't want to use the shortcut at index 4 because it's actually longer than the regular path. Therefore we drive the last 50 kilometers down the regular road - 20+50=70. |
|
|
| 3) | |
| | 900 | {0,20,80,50,160,140,420,450} | {10,60,190,70,180,160,901,900} | {9,45,100,15,14,14,5,0} |
| Returns: 432 | |
|