Problem Statement
You have decided to sit down and figure out the bare minimum you need to pay for your long-distance telephone service. You notice that each provider's rates are in the following format: "X cents for the first Y minutes, and Z cents a minute after that." So, for example, one long-distance provider might offer "99 cents for the first 20 minutes, and 7 cents a minute after that."
You also realize that for exceptionally long calls, money can sometimes be saved by hanging up and calling back in the middle. Say you needed to make a 40-minute call. If you were to go the entire call without hanging up, you would be charged $2.39 under the plan mentioned above. However, if you hung up after the first 20 minutes and called back, the total phone call would only cost you $1.98.
Since saving money is your ultimate goal, you are willing to switch telephone providers as much as necessary to pay the cheapest overall amount. However, you would still prefer to switch as few times as possible.
Given a list of possible calling plans, as well as a list of lengths of phone calls that you have to make, return the least number of times you will need to switch providers while still saving the most money.
Definition
- Class:
- LongDistance
- Method:
- changeProviders
- Parameters:
- int[], int[], int[], int[]
- Returns:
- int
- Method signature:
- int changeProviders(int[] initialCharges, int[] initialChargeLengths, int[] extraCharges, int[] callLengths)
- (be sure your method is public)
Notes
- The rate plan for provider i is: "initialCharges[i] cents for the first initialChargeLengths[i] minutes, and extraCharges[i] cents a minute after that."
- Each call (or part of a call) must be a whole number of minutes.
- You may make the calls in any order.
- You may hang up and call back as many times as you'd like for each call.
- You cannot change providers in the middle of a telephone call. That is, if you decide to save money on a call by hanging up and calling again, you cannot use the time in between to change providers.
- You start out with no long-distance service at all, so you will need to change providers in order to make the first call.
Constraints
- initialCharges will contain between 1 and 10 elements, inclusive.
- initialCharges, initialChargeLengths, and extraCharges will all contain the same number of elements.
- Each element of initialCharges will be between 0 and 1000, inclusive.
- Each element of initialChargeLengths will be between 1 and 1000, inclusive.
- Each element of extraCharges will be between 0 and 1000, inclusive.
- callLengths will contain between 1 and 50 elements, inclusive.
- Each element of callLengths will be between 1 and 1000000, inclusive.
Examples
{99,200}
{20,1}
{7,0}
{40,41}
Returns: 2
You have two providers to choose from. One provider uses the "99 cents for the first 20 minutes, and 7 cents a minute after that" plan. The other provider offers "200 cents for the first 1 minute, and 0 cents a minute after that." In other words, a $2.00 flat rate per phone call. The 40 minute call would cost a minimum of $1.98 under the first plan (by hanging up and calling back after the first 20 minutes). The 41 minute call would cost a minimum of $2.05 under the first plan (also by hanging up after the first 20 minutes). Both calls would cost $2.00 under the second plan. Therefore, to save the most money, you would need to switch to the first provider to make the first call, and then switch to the second provider to make the second call. Since you need to switch providers twice, your method should return 2.
{99,200,130}
{20,1,10}
{7,0,2}
{40,41}
Returns: 1
A new, third provider has now been offered. Under this provider, the 40 minute call would cost $1.90 and the 41 minute call would cost $1.92. (Note that you can save the most money on both of these calls by never hanging up.) Since both of these rates are the best offered so far, this is the only provider you need to use. You always need to switch providers to make the first call, so your method should return 1.
{99,200,130}
{20,1,10}
{7,0,2}
{45,1000000}
Returns: 1
The 45 minute call would cost $2.33 under the first plan (two hang-ups), $2.00 under the second plan, and also $2.00 under the third plan. So either the second or the third plan would be acceptable for making this call. The 1000000 minute call, on the other hand, would definitely need to be done using the third plan, since it will only cost $2.00. The best thing to do would be to use the third plan for both calls. This way, providers need only to be switched once, at the beginning.
{99,200}
{20,1}
{7,0}
{40,41,39,42,38,43,37,44,36,45,35,46,34,47,33,48,32,49,31,50}
Returns: 2
The phone calls that last 40 or fewer minutes should be done under the first provider (since they will cost less than $2.00), whereas the phone calls that last 41 minutes or more should be done under the second provider (since they will only cost $2.00). If the calls had to be made in the order given, you would need to switch providers 20 times! However, you are allowed to make the calls in any order; only two provider changes are necessary.
{1,0}
{1,1}
{0,1000}
{100000,200000,300000,400000,500000}
Returns: 1
The first provider offers a flat rate of one cent per call. The second provider gives you the first minute of each call free, but charges $10.00 for each additional minute. You decide to use the second provider for each call, since you can hang up and call back every minute to avoid paying a single penny.
{2,3,4,5,6,7,8,9,10,11}
{1,2,3,4,5,6,7,8,9,10}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{1,2,3,4,5,6,7,8,9,10}
Returns: 10
Each provider is best suited for a single call length, so all 20 providers must be used.
{9,5,1,2,8,10,3,7,6,4}
{6,4,7,10,1,5,9,8,2,3}
{10,6,1,8,4,9,5,2,3,7}
{999968,999956,999962,999957,999973,999960,999977,999984,999985,999975,999993,999987,999996,999961,999980,999990,999995,999986,999958,999981,999979,999978,999964,999971,999997,999992,999998,999994,999970,999969,999972,999983,999951,999965,999974,999991,999959,999963,999967,999988,999953,999966,1000000,999954,999955,999989,999982,999999,999976,999952}
Returns: 1
{100,100,100,100,100,10}
{10,11,12,13,14,1}
{0,0,0,0,0,10}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
Returns: 2
{0,0,0,0,1,1,1,1}
{1,1,2,2,1,1,2,2}
{0,1,0,1,0,1,0,1}
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}
Returns: 1
{0}
{1}
{0}
{1}
Returns: 1
{1}
{1}
{0}
{1}
Returns: 1
{1}
{1}
{2}
{1}
Returns: 1
{2}
{1}
{1}
{1}
Returns: 1
{1}
{1}
{1}
{1}
Returns: 1
{1000,500,200}
{10,5,2}
{0,100,75}
{8,9,10,11,100}
Returns: 2
{0,1000}
{1000,1}
{0,1000}
{1000000,1}
Returns: 1
{198,400}
{20,1}
{14,0}
{40,41}
Returns: 2
{198,400,260}
{20,1,10}
{14,0,4}
{40,41}
Returns: 1
{198,400,260}
{20,1,10}
{14,0,4}
{45,1000000}
Returns: 1
{198,400}
{20,1}
{14,0}
{40,41,39,42,38,43,37,44,36,45,35,46,34,47,33,48,32,49,31,50}
Returns: 2
{2,3,4,5,6,7,8,9,10,11}
{1,2,3,4,5,6,7,8,9,10}
{1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}
{1,2,3,4,5,1,2,3,4,5,10000}
Returns: 6
{ 1 }
{ 1 }
{ 1 }
{ 1 }
Returns: 1
{ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
{ 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000 }
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
Returns: 10
{ 99, 200 }
{ 20, 1 }
{ 7, 0 }
{ 40, 41, 39, 42, 38, 43, 37, 44, 36, 45, 35, 46, 34, 47, 33, 48, 32, 49, 31, 50 }
Returns: 2
{ 2, 3, 4, 5, 6, 20, 8, 9, 10, 11 }
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
{ 950, 920, 1000, 600, 1000, 940, 1000, 999, 980, 1000 }
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 50493, 2345 }
Returns: 9
{ 5, 10 }
{ 5, 10 }
{ 1, 0 }
{ 10, 100 }
Returns: 1
{ 99, 200 }
{ 20, 1 }
{ 7, 0 }
{ 40, 41, 39, 42, 38, 43, 37, 44, 36, 45 }
Returns: 2
{ 30, 30 }
{ 20, 20 }
{ 2, 1 }
{ 20, 21 }
Returns: 1
{ 1, 10 }
{ 10, 10 }
{ 1000, 10 }
{ 5, 42 }
Returns: 1
{ 5, 4 }
{ 5, 4 }
{ 1, 1 }
{ 5, 4 }
Returns: 1
{ 99, 200 }
{ 20, 1 }
{ 7, 0 }
{ 40, 41, 39, 42, 38, 43, 37, 44, 36, 35, 45 }
Returns: 2
{ 20, 15 }
{ 20, 15 }
{ 0, 1 }
{ 15, 20 }
Returns: 1
{ 100, 200 }
{ 20, 1 }
{ 7, 0 }
{ 41, 40 }
Returns: 1
{ 1, 6, 23, 290, 123, 23, 392, 8, 1, 39 }
{ 2, 23, 129, 93, 28, 19, 239, 9, 3, 29 }
{ 1, 29, 38, 382, 1, 2, 39, 95, 30, 201 }
{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 2837, 28, 382, 192, 284, 756, 2382, 2, 3, 192, 292, 48, 48, 28, 39, 591, 23, 392, 29, 9, 8, 7, 6, 4, 29, 402, 203, 201, 3, 4, 5892, 289, 393, 492 }
Returns: 3