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

ANSWER

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[0];
    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];
             
        // Initialize answer
        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))
            {
                // Update answer
                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));
    }
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro