Title
The questions are a bit difficult, but quite interesting
There is an array of coffee machines arr[], where arr[i] represents the time required for each coffee machine to brew coffee. There is an integer N, which represents the time it takes to brew coffee. There are N people (assuming that the time for this person to finish drinking the coffee after getting it is 0, and the coffee cup in his hand becomes empty). There is a machine for washing coffee cups. It can only wash one cup at a time. Each time it is washed, the coffee cup consumes The time is a. If the coffee cup evaporates and becomes clean by itself, the time consumed is b. Returns the shortest time from the start of the queue to when all the coffee cups become clean.
Analysis:
- After sorting out the meaning of the question, we can know that each coffee machine brews coffee in parallel operation, but a separate coffee machine can only brew coffee after the current coffee brewing is completed. The next cup is aserial operation.
- The machine that washes the coffee cups consumes time a, but it cannot be cleaned until the coffee is brewed. For example: Coffee machine No. 1 takes 2 minutes to brew a cup of coffee. It starts brewing a cup of coffee at the 0 time point and ends at the 2-minute time point. Then the machine that washes coffee cups starts working at the 2-minute time point and completes the work at the 2 + a time point before the next coffee cup can be cleaned. It should be noted that if you choose to clean both coffee cups 1 and 2, but coffee cup No. 1 is finished at 9 time, and coffee cup No. 2 is finished at 6 time, then coffee cup No. 2 is When cleaning, the starting time point is 9 + a, which is determined based on the last time the coffee cup needs to be cleaned.
- The evaporation of the coffee cup is a parallel operation, and the time it takes to become clean is b.
Violent recursion
We still start the analysis from violent recursion, and convert from violent recursion to dynamic programming, but before violent recursion, let’s break this question into 2 questions.
The first is to implement a simulated queuing function based on the coffee machine array arr and the number of people N preparing to make coffee. The function is to get the time when everyone can get coffee the fastest.
Simulated queuing
The function of simulating queuing uses PriorityQueue, and it implements the comparison rules of coffee machines. According to the characteristics of PriorityQueue, the most efficient coffee machine is always on top and used. Among them (0,1) means that the current available time point of the coffee machine is 0, and the time to brew a cup of coffee is 1.
Explain the picture above:
The coffee machine array arr{1,3,7} represents that the time required for coffee machine No. 0 to brew a cup of coffee is 1, the time required for coffee machine No. 1 is 3, and the time required for coffee machine No. 2 is 7. At the beginning, the coffee available time starts from the 0 time point. A total of 5 people lined up to make coffee.
Maximize the efficiency of your coffee machine based on how long it takes to brew a cup and when the machine is next available.
so:
- When the first person comes over, he will go to coffee machine No. 0 to make coffee. At this time, the coffee machine has finished brewing at time point 1, and the next available time point of the coffee machine is 1.
- When the second person comes, the available time point of coffee machine No. 0 is 1, and the time required to brew a cup of coffee is 1, 1 + 1 = 2, which is less than the time 3 of coffee machine No. 1 brewing a cup, so No. 0 will still be selected. The coffee machine brews coffee.
- When the third person comes, coffee machine No. 0 is available at time point 2, and the time to brew a cup of coffee is still 1, but at this time, coffee machine No. 1 is available at time point 0, and the time to brew coffee is 3. At this time, coffee machine No. 0 and coffee machine No. 1 finish brewing a cup of coffee at the same time (anyone can use it). We assume that coffee machine No. 1 is used. After use, the available time point of coffee machine No. 1 is 3, * *According to the characteristics of PriorityQueue, coffee machine No. 0 will be queued to the top**.
- So the fourth and fifth people who come over will choose coffee machine No. 0.
Code
public static class Machine {<!-- -->
// The time when the coffee machine can work
int timePoint;
//The time required to make a cup of coffee
int workTime;
public Machine(int timePoint, int workTime) {<!-- -->
this.timePoint = timePoint;
this.workTime = workTime;
}
}
//custom comparator
public static class MachineComparator implements Comparator<Machine> {<!-- -->
@Override
public int compare(Machine o1, Machine o2) {<!-- -->
return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.hashCode());
}
}
public static int forceMake(int[] arr, int N, int a, int b) {<!-- -->
PriorityQueue<Machine> heap = new PriorityQueue<>(new MachineComparator());
//When initializing, fill the heap
for (int i = 0; i < arr.length; i + + ) {<!-- -->
heap.add(new Machine(0, arr[i]));
}
//The fastest way for everyone to drink coffee
int[] drinks = new int[N];
for (int i = 0; i < N; i + + ) {<!-- -->
//Get the coffee machine element at the top of the heap
Machine curMachine = heap.poll();
//The next available time of the coffee machine
curMachine.timePoint + = curMachine.workTime;
//What time can I get coffee?
drinks[i] = curMachine.timePoint;
//Push into the heap again
heap.add(curMachine);
}
//The process method is a recursive method that finds the minimum time for the coffee cup to become clean.
return process(drinks, a, b, 0, 0);
}
The first simulated queuing problem is solved, and the next step is formal violent recursion.
The violent recursive method returns the minimum time for the drinks[index…] position to become clean.
So at this time the base case can also be determined index == drinks.length. Each cup can be cleaned or evaporated to make it clean.
Therefore, you need to pay attention to changes in the available time of the coffee cup cleaning machine when passing down the recursion.
Code
When passing down the code, if I choose cleaning, the available time of the machine will be extended backwards. If I choose air drying, the maximum value must be taken based on the available time of the coffee cup (barrel principle). Finally, after washing and air-drying, take the small ones.
//drinks: The shortest time for everyone to drink coffee
//wash: the time it takes to wash a coffee cup using a coffee cup washing machine
// air: the time it takes for air to evaporate in a coffee cup
//index: which cup
//free: The next time the coffee cup washing machine is available
public static int process(int[] drink, int wash, int air, int index, int free) {<!-- -->
//No more cups
if (index == drink.length) {<!-- -->
return 0;
}
//Select wash
int selfClean1 = Math.max(drink[index], free) + wash;
// Pass down, the time when the next cup is cleaned. At this time, the available time of the coffee cup cleaning machine is selfClean1
int restClean1 = process(drink, wash, air, index + 1, selfClean1);
//Wooden barrel principle, because cleaning is selected, it depends on whether the current cup selfClean or the next cup restClean takes longer, which one to choose
int p1 = Math.max(selfClean1, restClean1);
// Select air drying
int selfClean2 = drink[index] + air;
//free is still free, and the time for cleaning the coffee cup machine has not changed.
int restClean2 = process(drink, wash, air, index + 1, free);
//Similarly
int p2 = Math.max(selfClean2, restClean2);
//Choose the smallest one between air drying and cleaning.
return Math.min(p1, p2);
}
Dynamic Planning
Rewrite dynamic programming based on the code in violent recursion. As can be seen from the violent recursion code, the variable parameters are the array subscript index and the freeTime of the coffee cup cleaning machine. And the range of index is 0 ~ drinks.length. It should be noted that freeTime is different from the variable parameter range of the previous question. The time range of freeTime in this question is not easy to determine and needs to be calculated based on the specific business (based on the maximum time to finish coffee in drinks + the time to clean a coffee cup).
So when dp[][] is initialized, the range dp[N + 1][maxFree] can be determined.
Another thing to note is that when traversing the dp filling value, the inner loop traverses maxFree, and the variable free can approach maxFree infinitely, so when calculating restClean, you need to make a judgment, otherwise it will be very difficult There may be array subscript out of bounds situations.
In the violent recursion process, no matter how you clean the coffee cup, the time cannot be greater than maxFree. Therefore, if the calculated selfClean1 variable is > maxFree after adding wash, it will prove to be invalid. This situation does not exist in the actual process. break. This value does not need to be filled.
public static int dp(int[] drinks, int wash, int air) {<!-- -->
int N = drinks.length;
int maxFree = 0;
for (int i = 0; i < N; i + + ) {<!-- -->
maxFree = Math.max(maxFree, drinks[i]) + wash;
}
int[][] dp = new int[N + 1][maxFree + 1];
for (int index = N - 1; index >= 0; index--) {<!-- -->
for (int free = 0; free < maxFree; free + + ) {<!-- -->
int selfClean1 = Math.max(drinks[index], free) + wash;
if (selfClean1 > maxFree){<!-- -->
break;
}
int restClean1 = dp[index + 1][selfClean1];
int p1 = Math.max(selfClean1, restClean1);
int selfClean2 = drinks[index] + air;
int restClean2 = dp[index + 1][free];
int p2 = Math.max(selfClean2, restClean2);
dp[index][free] = Math.min(p1, p2);
}
}
return dp[0][0];
}
Full code
public static class Machine {
// The next time the coffee machine can work
int timePoint;
//The time required to make a cup of coffee
int workTime;
public Machine(int timePoint, int workTime) {
this.timePoint = timePoint;
this.workTime = workTime;
}
}
public static class MachineComparator implements Comparator {
@Override
public int compare(Machine o1, Machine o2) {
return (o1.timePoint + o1.workTime) - (o2.timePoint + o2.hashCode());
}
}
public static int minTime(int[] arr, int N, int a, int b) {
PriorityQueue heap = new PriorityQueue<>(new MachineComparator());
for (int i = 0; i < arr.length; i + + ) {
heap.add(new Machine(0, arr[i]));
}
int[] drinks = new int[N];
for (int i = 0; i < N; i + + ) {
Machine curMachine = heap.poll();
drinks[i] = curMachine.timePoint;
curMachine.timePoint + = curMachine.workTime;
heap.add(curMachine);
}
return process(drinks, a, b, 0, 0);
}
//drinks: The minimum time for each person to drink coffee
//wash: the time it takes to wash a coffee cup using a coffee cup washing machine
// air: the time it takes for air to evaporate in a coffee cup
//index: which cup
//free: The next time the coffee cup washing machine is available
public static int process(int[] drink, int wash, int air, int index, int free) {
//No more cups
if (index == drink.length) {
return 0;
}
//Select wash
int selfClean1 = Math.max(drink[index], free) + wash;
int restClean1 = process(drink, wash, air, index + 1, selfClean1);
int p1 = Math.max(selfClean1, restClean1);
// Select air drying
int selfClean2 = drink[index] + air;
int restClean2 = process(drink, wash, air, index + 1, free);
int p2 = Math.max(selfClean2, restClean2);
return Math.min(p1, p2);
}
public static int minTime2(int[] arr, int N, int a, int b) {
PriorityQueue heap = new PriorityQueue<>(new MachineComparator());
for (int i = 0; i < arr.length; i + + ) {
heap.add(new Machine(0, arr[i]));
}
int[] drinks = new int[N];
for (int i = 0; i < N; i + + ) {
Machine curMachine = heap.poll();
drinks[i] = curMachine.timePoint;
curMachine.timePoint + = curMachine.workTime;
heap.add(curMachine);
}
return dp(drinks, a, b);
}
public static int dp(int[] drinks, int wash, int air) {<!-- -->
int N = drinks.length;
int maxFree = 0;
for (int i = 0; i < N; i + + ) {<!-- -->
maxFree = Math.max(maxFree, drinks[i]) + wash;
}
int[][] dp = new int[N + 1][maxFree + 1];
for (int index = N - 1; index >= 0; index--) {<!-- -->
for (int free = 0; free < maxFree; free + + ) {<!-- -->
int selfClean1 = Math.max(drinks[index], free) + wash;
if (selfClean1 > maxFree){<!-- -->
break;
}
int restClean1 = dp[index + 1][selfClean1];
int p1 = Math.max(selfClean1, restClean1);
int selfClean2 = drinks[index] + air;
int restClean2 = dp[index + 1][free];
int p2 = Math.max(selfClean2, restClean2);
dp[index][free] = Math.min(p1, p2);
}
}
return dp[0][0];
}