Bob has N workers working under him. The ith worker has some strength wi currently, he has M tasks pending with him.Each task can be assigned to only 1 worker. To do particular task i, Strength si is required i.e a task i can be done by a worker only if his strength is greater or equal to Si, Bob has K magical pills, talking a magical pill will increase the strength of a worker by B units. Bob gives pills to workers optimally such that the maximum number of tasks can be done.

Task
Determine the maximum number of tasks that can be completed.
Example1:
K=10
B=1
N=3
W=[10,5,4]
M=3
S=[15,4,20]
Where,
K, Represents the number of magical pills.
B, represents an integer denoting the amount of strength that will be increased by taking a pill.
N represents the number of workers
W represents an array of integers denoting the strength of the workers.
M represents the number of tasks
S represents an array of integers denoting strength required for the task to complete.
Approach:
- Bob can assign task 2 to worker 2 and he can give 5 pills to worker 1 which will increase his strength to 15 and then assign task 1 to him. So at max 1 tasks can be completed. There is no way in which he can get more than 2 tasks done.
- Alternatively, he can give 10 pills to worker 3 and assign him task 3, and assign worker 1 to task 2.
- Therefore, the maximum number of tasks that can be assigned is 2
Example2:
Input:
K=2
B=1
N=2
W=[3,2]
M=2
S=[2,3]
Output:
2
Algorithm to Solve
- Take all inputs such as K representing number of magical pills
- B representing amount energy increased per taking 1 pill.
- N representing the number of workers
- W representing array of worker energies
- M representing number of tasks
- S representing the strength required to do particular task.
- Sort the array in “Ascending” order so that workers with less enery will come at beginning
- Also sort strength array.
- Now using two for loops iterate through all the worker array elements.
- Compare the energy level of worker and mount of energy needed to do particular task if both are sam then assign the task to worker , otherwise write another for loop which will find energy difference between task and worker energy, then exactly give how much pills are required to do the task.
- Then change worker enery to w[]=w[]-s[] that is worker energy – energy required to do particular task.
- Repeat untill maximum tasks are done.
JAVA Code
package arrayproblems; import java.util.*; class problem17 { public static void main(String[] args) { int k=10; int B=1; int N=3; int[] array1= {10,5,4}; int M=3; int[] array2= {15,4,20}; int res=0; Arrays.sort(array1); Arrays.sort(array2); for(int i=0;i<array1.length;i++) { for(int j=0;j<array2.length;j++) { if(array1[i]==array2[j]) { res=res+1; array1[i]=array2[j]-array1[i]; array2[j]=0; } else { for(int z=1;z<=k;z++) { if(B*z==array2[j]-array1[i]) { array1[i]=array1[i]+B*z; k=k-z; res=res+1; array1[i]=array1[i]-array2[j]; array2[j]=0; } } } } } System.out.println("no of tasks can be done is : " + res); } }
Watch Below Video to get complete Explanation for Above Code
Similar Off Campus Coding Questions
Xoriant off campus coding question and solution
Beginner’s friendly top 5 array questions in java
Pingback: APPSIAN off Campus Coding Question - Is It Actually
Pingback: Dynamic Programming HACKER EARTH questions - Is It Actually
Thanks.