Maximum Work Hacker Earth Problem solved

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

Count Buildings Hacker Earth coding question with solution

Complete Solution For Rob And Mars Problem In Java