Dada una tarea de array [] de tamaño N que indica la cantidad de trabajo a realizar para cada tarea, el problema es encontrar la cantidad mínima de trabajo a realizar cada día para que todas las tareas se puedan completar en D días como máximo.
Nota: En un día se puede trabajar para una sola tarea.
Ejemplos:
Entrada: tarea[] = [3, 4, 7, 15], D = 10
Salida: 4
Explicación: Aquí el trabajo mínimo a realizar es 4.
El primer día, tarea[0] = 3 < 4 por lo que esta tarea solo puede ser completado. Porque el trabajo se puede hacer para una sola tarea en un día.
Para task[1] = 4, la tarea se puede completar en 1 día.
Task[2] = 7. Ahora se pueden realizar 4 cantidades de trabajo en 1 día, por lo que para completar esta tarea se requieren 2 días.
Tarea[3] = 15, se requieren 4 días adicionales.
Número total de días requeridos = 1 + 1 + 2 + 4 = 8 días < D.
Entonces, el valor 4 sería el valor mínimo.Entrada: tarea[] = [30, 20, 22, 4, 21], D = 6
Salida: 22
Enfoque : el problema se puede resolver utilizando el enfoque de búsqueda binaria utilizando la siguiente idea:
El trabajo mínimo que se puede realizar cada día es 1 y el trabajo máximo que se puede realizar es el máximo de la array de tareas .
Busque en este rango y si el valor medio cumple la condición, muévase a la primera mitad del rango, de lo contrario a la segunda mitad.
Siga los pasos mencionados para implementar el enfoque:
- Cree una variable izquierda = 1 , represente el punto de inicio del rango, variable derecha = INT_MIN .
- Ejecute un ciclo desde index = 0 hasta index = N – 1 y actualice right = max(right, task[index]).
- Cree una variable per_day_task = 0 para almacenar la respuesta.
- Ejecutar una condición while con izquierda <= derecha
- crea una variable mid = left + (right – left)/2.
- si toda la tarea se puede realizar en D días realizando una cantidad media de trabajo cada día, actualice per_day_task = mid y haga bien = mid – 1.
- otra cosa a la derecha = medio + 1.
- Imprima per_day_task como el número mínimo de tareas realizadas cada día para completar todas las tareas.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción
4
Complejidad de tiempo: O(N * logN) Espacio
auxiliar : O(1)