Minimum work to be done per day to finish given tasks within D days

0 0 7 minutes read

Given an array task[] of size N denoting amount of work to be done for each task, the problem is to find the minimum amount of work to be done on each day so that all the tasks can be completed in at most D days.

Note: On one day work can be done for only one task.

Examples:

Input: task[] = [3, 4, 7, 15], D = 10
Output: 4
Explanation: Here minimum work to be done is 4.
On 1st day, task[0] = 3 < 4 so this task can only be completed. Because work can be done for only one task on one day.
For task[1] = 4 the task can be completed in 1 day.
Task[2] = 7. Now 4 amount of work can be done in 1 day so to complete this task 2 days are required.
Task[3] = 15, 4 additional days are required.
Total number of days required = 1 + 1 + 2 + 4 = 8 days < D.
So 4 value would be the minimum value.

Input: task[] = [30, 20, 22, 4, 21], D = 6
Output: 22

Approach: The problem can be solved using the binary search approach using the following idea:

The minimum work that can be done each day is 1 and the maximum work that can be done is the maximum of the tasks array.
Search on this range and if the mid-value satisfies the condition then move to 1st half of the range else to the second half.

Follow the steps mentioned to implement the approach:

Create a variable left = 1, represent the starting point of the range, variable right = INT_MIN.
Run a loop from index = 0 to index = N – 1 and update right = max(right, task[index]).
Create a variable per_day_task = 0, to store the answer.
Run a while condition with left <= right
- create a variable mid = left + (right – left)/2.
- if all the task can be done within D days by doing mid amount of work on each day update per_day_task = mid and make right = mid – 1.
- else right = mid + 1.
Print per_day_task as the minimum number of tasks done each day to complete all the tasks.

Below is the implementation for the above approach:

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if
// all the task can be
// completed by 'per_day'
// number of task per day
bool valid(int per_day,
           vector<int> task, int d)
{
 
    // Variable to store days required
    // to done all tasks
    int cur_day = 0;
    for (int index = 0; index < task.size();
         index++) {
 
        int day_req
            = ceil((double)(task[index])
                   / (double)(per_day));
 
        cur_day += day_req;
 
        // If more days required
        // than 'd' days so invalid
 
        if (cur_day > d) {
            return false;
        }
    }
 
    // Valid if days are less
    // than or equal to 'd'
    return cur_day <= d;
}
 
// Function to find minimum
// task done each day
int minimumTask(vector<int> task, int d)
{
 
    int left = 1;
    int right = INT_MAX;
 
    for (int index = 0;
         index < task.size();
         index++) {
        right = max(right, task[index]);
    }
 
    // Variable to store answer
    int per_day_task = 0;
 
    while (left <= right) {
 
        int mid = left
                  + (right - left) / 2;
 
        // If 'mid' number of task per day
        // is valid so store as answer and
        // more to first half
        if (valid(mid, task, d)) {
            per_day_task = mid;
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
 
    // Print answer
    return per_day_task;
}
 
// Driver Code
int main()
{
    // Input taken
    vector<int> task{ 3, 4, 7, 15 };
    int D = 10;
 
    cout << minimumTask(task, D) << endl;
 
    return 0;
}

Java

// JAVA code to implement the approach
import java.util.*;
class GFG 
{
 
  // Function to check if
  // all the task can be
  // completed by 'per_day'
  // number of task per day
  public static boolean
    valid(int per_day, ArrayList<Integer> task, int d)
  {
 
    // Variable to store days required
    // to done all tasks
    int cur_day = 0;
    for (int index = 0; index < task.size(); index++) {
 
      double day_req
        = (Math.ceil((double)task.get(index)
                     / (double)(per_day)));
 
      cur_day += day_req;
 
      // If more days required
      // than 'd' days so invalid
 
      if (cur_day > d) {
        return false;
      }
    }
 
    // Valid if days are less
    // than or equal to 'd'
    return cur_day <= d;
  }
 
  // Function to find minimum
  // task done each day
  public static int minimumTask(ArrayList<Integer> task,
                                int d)
  {
 
    int left = 1;
    int right = Integer.MAX_VALUE;
 
    for (int index = 0; index < task.size(); index++) {
      right = Math.max(right, task.get(index));
    }
 
    // Variable to store answer
    int per_day_task = 0;
 
    while (left <= right) {
 
      int mid = left + (right - left) / 2;
 
      // If 'mid' number of task per day
      // is valid so store as answer and
      // more to first half
      if (valid(mid, task, d)) {
        per_day_task = mid;
        right = mid - 1;
      }
      else {
        left = mid + 1;
      }
    }
 
    // Print answer
    return per_day_task;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    // Input taken
    ArrayList<Integer> task = new ArrayList<Integer>(
      Arrays.asList(3, 4, 7, 15));
    int D = 10;
 
    System.out.println(minimumTask(task, D));
  }
}
 
// This code is contributed by Taranpreet

Python

# Python code to implement the approach
import math
 
# Function to check if
# all the task can be
# completed by 'per_day'
# number of task per day
def valid(per_day, task, d):
 
    # Variable to store days required
    # to done all tasks
    cur_day = 0
    for index in range(0, len(task)):
 
        day_req = math.ceil((task[index]) / (per_day))
 
        cur_day += day_req
 
        # If more days required
        # than 'd' days so invalid
        if (cur_day > d):
            return False
 
    # Valid if days are less
    # than or equal to 'd'
    return cur_day <= d
 
# Function to find minimum
# task done each day
def minimumTask(task, d):
 
    left = 1
    right = 1e9 + 7
 
    for index in range(0, len(task)):
        right = max(right, task[index])
 
    # Variable to store answer
    per_day_task = 0
 
    while (left <= right):
 
        mid = left + (right - left) // 2
 
        # If 'mid' number of task per day
        # is valid so store as answer and
        # more to first half
        if (valid(mid, task, d)):
            per_day_task = mid
            right = mid - 1
 
        else:
            left = mid + 1
 
    # Print answer
    return math.trunc(per_day_task)
 
# Driver Code
# Input taken
task = [3, 4, 7, 15]
D = 10
 
print(minimumTask(task, D))
 
# This code is contributed by Samim Hossain Mondal.

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to check if
  // all the task can be
  // completed by 'per_day'
  // number of task per day
  public static bool
    valid(int per_day, List<int> task, int d)
  {
 
    // Variable to store days required
    // to done all tasks
    int cur_day = 0;
    for (int index = 0; index < task.Count; index++) {
 
      double day_req
        = (Math.Ceiling((double)task[(index)]
                        / (double)(per_day)));
 
      cur_day += (int)day_req;
 
      // If more days required
      // than 'd' days so invalid
 
      if (cur_day > d) {
        return false;
      }
    }
 
    // Valid if days are less
    // than or equal to 'd'
    return cur_day <= d;
  }
 
  // Function to find minimum
  // task done each day
  public static int minimumTask(List<int> task,
                                int d)
  {
 
    int left = 1;
    int right = Int32.MaxValue;
 
    for (int index = 0; index < task.Count; index++) {
      right = Math.Max(right, task[index]);
    }
 
    // Variable to store answer
    int per_day_task = 0;
 
    while (left <= right) {
 
      int mid = left + (right - left) / 2;
 
      // If 'mid' number of task per day
      // is valid so store as answer and
      // more to first half
      if (valid(mid, task, d)) {
        per_day_task = mid;
        right = mid - 1;
      }
      else {
        left = mid + 1;
      }
    }
 
    // Print answer
    return per_day_task;
  }
 
  // Driver Code
  public static void Main(String []args)
  {
     
    // Input taken
    List<int> task = new List<int>();
    task.Add(3);
    task.Add(4);
    task.Add(7);
    task.Add(15);
    int D = 10;
 
    Console.WriteLine(minimumTask(task, D));
  }
}
 
// This code is contributed by code_hunt.

Javascript

<script>
       // JavaScript code for the above approach
 
       // Function to check if
       // all the task can be
       // completed by 'per_day'
       // number of task per day
       function valid(per_day,
           task, d) {
 
           // Variable to store days required
           // to done all tasks
           let cur_day = 0;
           for (let index = 0; index < task.length;
               index++) {
 
               let day_req
                   = Math.ceil((task[index])
                       / (per_day));
 
               cur_day += day_req;
 
               // If more days required
               // than 'd' days so invalid
 
               if (cur_day > d) {
                   return false;
               }
           }
 
           // Valid if days are less
           // than or equal to 'd'
           return cur_day <= d;
       }
 
       // Function to find minimum
       // task done each day
       function minimumTask(task, d) {
 
           let left = 1;
           let right = Number.MAX_VALUE;
 
           for (let index = 0;
               index < task.length;
               index++) {
               right = Math.max(right, task[index]);
           }
 
           // Variable to store answer
           let per_day_task = 0;
 
           while (left <= right) {
 
               let mid = left
                   + (right - left) / 2;
 
               // If 'mid' number of task per day
               // is valid so store as answer and
               // more to first half
               if (valid(mid, task, d)) {
                   per_day_task = mid;
                   right = mid - 1;
               }
               else {
                   left = mid + 1;
               }
           }
 
           // Print answer
           return per_day_task;
       }
 
       // Driver Code
 
       // Input taken
       let task = [3, 4, 7, 15];
       let D = 10;
 
       document.write(minimumTask(task, D) + '<br>');
 
    // This code is contributed by Potta Lokesh
   </script>

Output

Time Complexity: O(N * logN)
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!