Dado un entero positivo K y una array arr[] que consta de N enteros positivos, tal que arr[i] es el número de procesos que el i -ésimo procesador puede programar en 1 segundo . La tarea es minimizar el tiempo total requerido para programar K procesos de tal manera que después de la programación por parte del i -ésimo procesador, arr[i] se reduzca a floor(arr[i]/2) .
Ejemplos:
Entrada: N = 5, arr[] = {3, 1, 7, 2, 4}, K = 15
Salida: 4
Explicación:
El orden del proceso programado es el siguiente:
- El tercer proceso se programa primero. La array arr[] se modifica a {3, 1, 3, 2, 4}, como arr[2] = floor(arr[2] / 2) = floor(7 / 2) = 3.
- El 5º proceso está programado a continuación. La array arr[] se modifica a {3, 1, 3, 2, 2}.
- El 1er proceso está programado a continuación. La array arr[] se modifica a {1, 1, 3, 2, 2}.
- El segundo proceso está programado a continuación. La array arr[] se modifica a {3, 0, 3, 2, 4}.
El total de procesos programados por todo el proceso = 7 + 4 + 3 + 1 = 15(= K) y el tiempo total requerido es de 4 segundos.
Entrada: N = 4, arr[] = {1, 5, 8, 6}, K = 10
Salida: 2
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es ordenar la lista dada en orden ascendente y elegir el procesador con la capacidad más alta y reducir el valor de K por ese valor y eliminar ese procesador de la lista y agregar la mitad de eso en la lista ordenada de nuevo. Repita el proceso anterior hasta que se programen al menos K procesos e imprima el tiempo requerido después de programar al menos K procesos.
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso del concepto Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar tmp[] del tamaño del elemento máximo presente en la array dada .
- Inicialice una variable, digamos contar para almacenar el tiempo mínimo para programar todos los procesos respectivamente.
- Recorra la array dada tmp[] desde el final y realice los siguientes pasos:
- Si el elemento actual en tmp[] es mayor que 0 e i * tmp[i] es menor que K .
- Disminuya el valor de K por el valor i * tmp[i] .
- Aumente tmp[i/2] por tmp[i] ya que la capacidad del procesador se reducirá a la mitad.
- Aumente el valor de count por el valor tmp[i] .
- Si el valor de K ya es menor o igual a 0 , imprima el valor de count como resultado.
- Si el elemento actual en la array tmp[] es al menos 0 y el valor de i * tmp[i] es al menos K , realice los siguientes pasos:
- Si K es divisible por el índice actual, incremente el valor de count en K / i .
- De lo contrario, incremente el valor de cuenta en K/i +1 .
- Si el elemento actual en tmp[] es mayor que 0 e i * tmp[i] es menor que K .
- Después de completar los pasos anteriores, imprima -1 si no es posible programar todos los procesos. De lo contrario, imprima el conteo como el tiempo mínimo requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum required
// time to schedule all process
int minTime(int A[], int n, int K)
{
// Stores max element from A[]
int max_ability = A[0];
// Find the maximum element
for(int i = 1; i < n; i++)
{
max_ability = max(max_ability, A[i]);
}
// Stores frequency of each element
int tmp[max_ability + 1] = {0};
// Stores minimum time required
// to schedule all process
int count = 0;
// Count frequencies of elements
for(int i = 0; i < n; i++)
{
tmp[A[i]]++;
}
// Find the minimum time
for(int i = max_ability; i >= 0; i--)
{
if (tmp[i] != 0)
{
if (tmp[i] * i < K)
{
// Decrease the value
// of K
K -= (i * tmp[i]);
// Increment tmp[i/2]
tmp[i / 2] += tmp[i];
// Increment the count
count += tmp[i];
// Return count, if all
// process are scheduled
if (K <= 0)
{
return count;
}
}
else
{
// Increment count
if (K % i != 0)
{
count += (K / i) + 1;
}
else
{
count += (K / i);
}
// Return the count
return count;
}
}
}
// If it is not possible to
// schedule all process
return -1;
}
// Driver code
int main()
{
int arr[] = { 3, 1, 7, 2, 4 };
int N = 5;
int K = 15;
cout << minTime(arr, N, K);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to find minimum required
// time to schedule all process
static int minTime(int[] A, int n, int K)
{
// Stores max element from A[]
int max_ability = A[0];
// Find the maximum element
for (int i = 1; i < n; i++) {
max_ability = Math.max(
max_ability, A[i]);
}
// Stores frequency of each element
int tmp[] = new int[max_ability + 1];
// Stores minimum time required
// to schedule all process
int count = 0;
// Count frequencies of elements
for (int i = 0; i < n; i++) {
tmp[A[i]]++;
}
// Find the minimum time
for (int i = max_ability;
i >= 0; i--) {
if (tmp[i] != 0) {
if (tmp[i] * i < K) {
// Decrease the value
// of K
K -= (i * tmp[i]);
// Increment tmp[i/2]
tmp[i / 2] += tmp[i];
// Increment the count
count += tmp[i];
// Return count, if all
// process are scheduled
if (K <= 0) {
return count;
}
}
else {
// Increment count
if (K % i != 0) {
count += (K / i) + 1;
}
else {
count += (K / i);
}
// Return the count
return count;
}
}
}
// If it is not possible to
// schedule all process
return -1;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 3, 1, 7, 2, 4 };
int N = arr.length;
int K = 15;
System.out.println(
minTime(arr, N, K));
}
}
Python3
# Python3 program for the above approach # Function to find minimum required # time to schedule all process def minTime(A, n, K): # Stores max element from A[] max_ability = A[0] # Find the maximum element for i in range(1, n): max_ability = max(max_ability, A[i]) # Stores frequency of each element tmp = [0 for i in range(max_ability + 1)] # Stores minimum time required # to schedule all process count = 0 # Count frequencies of elements for i in range(n): tmp[A[i]] += 1 # Find the minimum time i = max_ability while(i >= 0): if (tmp[i] != 0): if (tmp[i] * i < K): # Decrease the value # of K K -= (i * tmp[i]) # Increment tmp[i/2] tmp[i // 2] += tmp[i] # Increment the count count += tmp[i] # Return count, if all # process are scheduled if (K <= 0): return count else: # Increment count if (K % i != 0): count += (K // i) + 1 else: count += (K // i) # Return the count return count i -= 1 # If it is not possible to # schedule all process return -1 # Driver code if __name__ == '__main__': arr = [ 3, 1, 7, 2, 4 ] N = 5 K = 15 print(minTime(arr, N, K)) # This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the above approach
using System;
class GFG{
// Function to find minimum required
// time to schedule all process
static int minTime(int[] A, int n, int K)
{
// Stores max element from A[]
int max_ability = A[0];
// Find the maximum element
for(int i = 1; i < n; i++)
{
max_ability = Math.Max(
max_ability, A[i]);
}
// Stores frequency of each element
int []tmp = new int[max_ability + 1];
// Stores minimum time required
// to schedule all process
int count = 0;
// Count frequencies of elements
for(int i = 0; i < n; i++)
{
tmp[A[i]]++;
}
// Find the minimum time
for(int i = max_ability; i >= 0; i--)
{
if (tmp[i] != 0)
{
if (tmp[i] * i < K)
{
// Decrease the value
// of K
K -= (i * tmp[i]);
// Increment tmp[i/2]
tmp[i / 2] += tmp[i];
// Increment the count
count += tmp[i];
// Return count, if all
// process are scheduled
if (K <= 0)
{
return count;
}
}
else
{
// Increment count
if (K % i != 0)
{
count += (K / i) + 1;
}
else
{
count += (K / i);
}
// Return the count
return count;
}
}
}
// If it is not possible to
// schedule all process
return -1;
}
// Driver Code
public static void Main(string[] args)
{
int []arr = { 3, 1, 7, 2, 4 };
int N = arr.Length;
int K = 15;
Console.WriteLine(minTime(arr, N, K));
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum required
// time to schedule all process
function minTime(A, n, K)
{
// Stores max element from A[]
let max_ability = A[0];
// Find the maximum element
for (let i = 1; i < n; i++) {
max_ability = Math.max(
max_ability, A[i]);
}
// Stores frequency of each element
let tmp =
Array.from({length: max_ability + 1}, (_, i) => 0);
// Stores minimum time required
// to schedule all process
let count = 0;
// Count frequencies of elements
for (let i = 0; i < n; i++) {
tmp[A[i]]++;
}
// Find the minimum time
for (let i = max_ability;
i >= 0; i--) {
if (tmp[i] != 0) {
if (tmp[i] * i < K) {
// Decrease the value
// of K
K -= (i * tmp[i]);
// Increment tmp[i/2]
tmp[(i / 2)] += tmp[i];
// Increment the count
count += tmp[i];
// Return count, if all
// process are scheduled
if (K <= 0) {
return count;
}
}
else {
// Increment count
if (K % i != 0) {
count += Math.floor(K / i) + 1;
}
else {
count += Math.floor(K / i);
}
// Return the count
return count;
}
}
}
// If it is not possible to
// schedule all process
return -1;
}
// Driver Code
let arr = [ 3, 1, 7, 2, 4 ];
let N = arr.length;
let K = 15;
document.write( minTime(arr, N, K));
</script>
Producción
4
Complejidad temporal: O(M), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(M)
Enfoque alternativo (usando STL): el problema dado se puede resolver utilizando el enfoque codicioso con la ayuda de max-heap. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de prioridad, digamos PQ, e inserte todos los elementos de la array dada en PQ.
- Inicialice una variable, digamos ans como 0 para almacenar el diamante máximo obtenido resultante.
- Iterar un bucle hasta que la cola de prioridad PQ no esté vacía y el valor de K > 0:
- Extraiga el elemento superior de la cola de prioridad y agregue el elemento emergente a la variable ans.
- Divida el elemento reventado por 2 e insértelo en la cola de prioridad PQ.
- Disminuya el valor de K en 1.
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to execute k processes that can be gained in
// minimum amount of time
void executeProcesses(int A[], int N, int K)
{
// Stores all the array elements
priority_queue<int> pq;
// Push all the elements to the
// priority queue
for (int i = 0; i < N; i++) {
pq.push(A[i]);
}
// Stores the required result
int ans = 0;
// Loop while the queue is not
// empty and K is positive
while (!pq.empty() && K > 0) {
// Store the top element
// from the pq
int top = pq.top();
// Pop it from the pq
pq.pop();
// Add it to the answer
ans ++;
// Divide it by 2 and push it
// back to the pq
K = K - top;
top = top / 2;
pq.push(top);
}
// Print the answer
cout << ans;
}
// Driver Code
int main()
{
int A[] = { 3, 1, 7, 4, 2 };
int K = 15;
int N = sizeof(A) / sizeof(A[0]);
executeProcesses(A, N, K);
return 0;
}
Python3
# Python3 program for the above approach # Function to execute k processes that # can be gained in minimum amount of time def executeProcesses(A, N, K): # Stores all the array elements pq = [] # Push all the elements to the # priority queue for i in range(N): pq.append(A[i]) # Stores the required result ans = 0 pq.sort() # Loop while the queue is not # empty and K is positive while (len(pq) > 0 and K > 0): # Store the top element # from the pq top = pq.pop() # Add it to the answer ans += 1 # Divide it by 2 and push it # back to the pq K -= top top //=2 pq.append(top) pq.sort() # Print the answer print(ans) # Driver Code A = [ 3, 1, 7, 4, 2 ] K = 15 N=len(A) executeProcesses(A, N, K) # This code is contributed by patel2127
Javascript
<script>
// Javascript program for the above approach
// Function to execute k processes that
// can be gained in minimum amount of time
function executeProcesses(A, N, K)
{
// Stores all the array elements
let pq = [];
// Push all the elements to the
// priority queue
for(let i = 0; i < N; i++)
{
pq.push(A[i]);
}
// Stores the required result
let ans = 0;
pq.sort(function(a, b){return a - b;});
// Loop while the queue is not
// empty and K is positive
while (pq.length > 0 && K > 0)
{
// Store the top element
// from the pq
let top = pq.pop();
// Add it to the answer
ans++;
// Divide it by 2 and push it
// back to the pq
K -= top;
top = Math.floor(top / 2);
pq.push(top);
pq.sort(function(a, b){return a - b;});
}
// Print the answer
document.write(ans)
}
// Driver Code
let A = [ 3, 1, 7, 4, 2 ];
let K = 15;
let N = A.length;
executeProcesses(A, N, K);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
4
Complejidad de tiempo : O((N + K)*log N)
Espacio Auxiliar : O(N)