# Searching 51

QUESTION

Given an array of jobs with different time requirements. There are K identical assignees available and we are also given how much time an assignee takes to do one unit of job. Find the minimum time to finish all jobs with following constraints.\n\nAn assignee can be assigned only contiguous jobs. For example, an assignee cannot be assigned jobs 1 and 3, but not 2.\nTwo assignees cannot share (or co-assigned) a job, i.e., a job cannot be partially assigned to one assignee and partially to other. \nInput\nNumber of jobs, array of jobs, K identical assignees available and the time T, an assignee takes to do one unit of job.\n.

“TESTCASE_1”: “6\n10 7 8 12 6 8\n4\n5\n###—###SEPERATOR—###—\n75”, “TESTCASE_2”: “3\n4 5 10\n2\n5\n###—###SEPERATOR—###—\n50”, “TESTCASE_3”: “2\n6 9\n1\n2\n###—###SEPERATOR—###—\n30”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

``````import java.io.*;
import java.util.*;
// Java program to find minimum time
// to finish all jobs with given
// number of assignees

class TestClass
{
// Utility function to get
// maximum element in job[0..n-1]
static int getMax(int arr[], int n)
{
int result = arr;
for (int i=1; i<n; i++)
if (arr[i] > result)
result = arr[i];
return result;
}

// Returns true if it is possible to finish jobs[]
// within given time 'time'
static boolean isPossible(int time, int K,
int job[], int n)
{
// cnt is count of current
// assignees required for jobs
int cnt = 1;

// time assigned to current assignee
int curr_time = 0;

for (int i = 0; i < n;)
{
// If time assigned to current assignee
// exceeds max, increment count of assignees.
if (curr_time + job[i] > time) {
curr_time = 0;
cnt++;
}

// Else add time of job to current
// time and move to next job.
else
{
curr_time += job[i];
i++;
}
}

// Returns true if count
// is smaller than k
return (cnt <= K);
}

// Returns minimum time required to
// finish given array of jobs
// k --> number of assignees
// T --> Time required by every assignee to finish 1 unit
// m --> Number of jobs
static int findMinTime(int K, int T, int job[], int n)
{
// Set start and end for binary search
// end provides an upper limit on time
int end = 0, start = 0;
for (int i = 0; i < n; ++i)
end += job[i];

int ans = end;

// Find the job that takes maximum time
int job_max = getMax(job, n);

// Do binary search for
// minimum feasible time
while (start <= end)
{
int mid = (start + end) / 2;

// If it is possible to finish jobs in mid time
if (mid >= job_max && isPossible(mid, K, job, n))
{
ans = Math.min(ans, mid);

end = mid - 1;
}

else
start = mid + 1;
}

return (ans * T);
}

// Driver program
public static void main(String arg[])
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int arr[]=new int[n];
for(int i=0;i<n;i++)
arr[i]=sc.nextInt();
int k=sc.nextInt();
int t=sc.nextInt();
System.out.println(findMinTime(k, t, arr, n));
}
}``````  