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
100
{10,50}
{60,90}
{40,20}
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.
1000
{}
{}
{}
Returns: 1000
We're in for a long drive with no shortcuts.
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.
1000
{1,2,3,4,5,21,22,23,24,25,41,42}
{22,7,6,5,6,42,27,26,25,26,62,47}
{20,2,4,4,4,20,2,4,4,4,20,2}
Returns: 991
100
{0,0,0,0,0}
{5,6,7,8,9}
{4,5,5,7,8}
Returns: 98
100
{40}
{50}
{11}
Returns: 100
500
{0,10,20,30,40,50,60,70,80,90,100,110}
{5,15,25,35,45,55,65,75,85,95,105,115}
{4,4,4,4,4,4,4,4,4,4,4,4}
Returns: 488
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
1000
{635,261,13,638,776,866,855,690,422,583,747,887}
{829,484,763,654,952,982,907,707,594,693,955,989}
{112,173,611,7,66,7,27,10,107,31,123,23}
Returns: 744
1000
{626,480,609,90,256,344,882,144,369,294,167,412}
{992,535,615,184,290,541,929,283,629,740,652,944}
{89,55,3,75,10,187,13,90,185,93,39,139}
Returns: 520
1
{}
{}
{}
Returns: 1
30
{35}
{40}
{0}
Returns: 30
1000
{707,827,386,625,20,387,462,364,219,351,140,566}
{818,936,446,967,552,802,711,535,983,588,548,801}
{32,68,34,286,487,209,88,10,47,116,105,37}
Returns: 283
1000
{409,135,836,81,362,443,297,531,835,399,785,246}
{620,744,922,777,656,558,364,611,851,563,946,753}
{210,608,85,695,293,114,66,79,15,163,160,506}
Returns: 997
Can take a max of 3 of these paths - each saves 1
1000
{635,522,272,13,733,41,776,336,784,855,472,48}
{829,660,835,763,922,438,952,974,796,907,876,611}
{193,137,562,749,188,396,175,637,11,51,403,562}
Returns: 996
4 of these
1000
{12,21,22,39,44,65,86,96,97,104,112,133}
{23,27,37,40,60,82,93,97,103,109,128,151}
{6,5,12,0,6,1,4,1,4,1,9,4}
Returns: 938
1000
{12,61,68,65,68,69,89,106,113,132,161,190}
{61,66,69,70,70,84,109,114,134,164,190,235}
{12,5,1,4,1,14,6,5,15,7,2,12}
Returns: 882
1000
{26,57,67,121,144,208,275,311,323,352,385,451}
{53,72,105,123,184,252,293,314,338,365,426,497}
{16,12,31,1,15,2,9,2,9,4,24,10}
Returns: 836
1000
{20,65,87,102,146,185,200,224,249,274,333,357}
{55,77,92,136,175,190,214,239,264,323,347,365}
{34,6,5,1,3,4,1,6,14,20,2,5}
Returns: 866
1000
{850,800,750,700,650,600,550,500,450,400,350,300}
{885,829,765,701,691,602,593,519,494,447,376,303}
{19,8,12,1,29,1,34,18,2,17,20,2}
Returns: 858
1000
{635,522,272,13,733,41,776,336,784,855,472,48}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{480,261,697,685,638,373,711,866,51,328,690,533}
Returns: 414
1000
{10,10,10,10,10,10,10,10}
{20,20,20,30,30,20,30,40}
{8,7,7,18,28,8,27,28}
Returns: 997
1000
{422,560,237,747,530,820,626,220,96,609,518,93}
{472,610,287,797,580,870,676,270,146,659,568,143}
{30,65,28,82,99,23,98,53,100,2,10,80}
Returns: 843
999
{0,0,0,0,0,0,0,0,0,0,0,0}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
Returns: 999
Yeah... ideas are coming kind of slow.
1000
{7,6,3,0,8,0,9,4,9,9,5,1}
{73,65,76,73,79,62,83,83,61,70,78,69}
{50,50,50,50,50,50,50,50,50,50,50,50}
Returns: 971
145
{47,62,26,83,59,91,70,24,11,68,58,10}
{106,131,84,158,139,148,149,90,91,118,111,84}
{50,50,50,50,50,50,50,50,50,50,50,50}
Returns: 115
1000
{0,10,20,30,40,50,60,70,80,90,100,110}
{5,15,25,35,45,55,65,75,85,95,105,115}
{4,4,4,4,4,4,4,4,4,4,4,4}
Returns: 988
1000
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
Returns: 1000
10
{4, 1 }
{6, 2 }
{0, 0 }
Returns: 7
1000
{0, 100, 300 }
{100, 300, 666 }
{99, 201, 365 }
Returns: 998
150
{0, 0, 50, 100, 110 }
{50, 50, 100, 151, 140 }
{10, 20, 10, 10, 90 }
Returns: 70
1000
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }
{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 }
{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }
Returns: 1000
100
{10, 50 }
{60, 90 }
{40, 20 }
Returns: 80
1000
{0 }
{1000 }
{998 }
Returns: 998
1000
{10 }
{12 }
{1 }
Returns: 999
950
{0, 20, 80, 50, 160, 140, 420, 450, 100, 70, 949 }
{10, 60, 190, 70, 180, 160, 901, 900, 500, 100, 950 }
{9, 45, 100, 15, 14, 14, 5, 0, 550, 20, 5 }
Returns: 446
1000
{1, 20 }
{21, 900 }
{1, 1 }
Returns: 121