Programe el ascensor para reducir el tiempo total empleado

Dado un número entero k y una array arr[] que representa los pisos de destino para N personas que esperan actualmente en la planta baja y k es la capacidad del ascensor, es decir, el número máximo de personas que puede albergar al mismo tiempo. El ascensor tarda 1 unidad de tiempo en llegar a cualquier piso consecutivo desde el piso actual. La tarea es programar el ascensor de manera que se minimice el tiempo total necesario para llevar a todas las personas a su piso de destino y luego regresar a la planta baja.
Ejemplos: 
 

Entrada: arr[] = {2, 3, 4}, k = 2 
Salida: 12  La
segunda y la tercera persona (pisos de destino 3 y 4) irán en el primer turno tomando 8 (4 + 4) unidades de tiempo. La única persona que queda tardará 2 unidades de tiempo en llegar al destino 
y luego el ascensor tardará otras 2 unidades de tiempo en volver a la planta baja. 
Tiempo total empleado = 8 + 2 + 2 = 12
Entrada: arr[] = {5, 5, 4}, k = 3 
Salida: 10 
Todas las personas pueden subir al ascensor al mismo tiempo 
El tiempo necesario será 10 (5 + 5). 
 

Enfoque: ordene la array dada en orden decreciente de destino. Cree grupos de K (a partir del piso más alto), el costo de cada grupo será de 2 * (max(Elements in current group)) . La suma de todos los grupos será la respuesta.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum time taken
// by the elevator when operating optimally
int minTime(int n, int k, int a[])
{
    // Sort in descending order
    sort(a, a + n, greater<int>());
    int minTime = 0;
 
    // Iterate through the groups
    for (int i = 0; i < n; i += k)
 
        // Update the time taken for each group
        minTime += (2 * a[i]);
 
    // Return the total time taken
    return minTime;
}
 
// Driver code
int main()
{
    int k = 2;
    int arr[] = { 2, 3, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << minTime(n, k, arr);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
// Function to return the minimum time taken
// by the elevator when operating optimally
public static int minTime(int n, int k, Integer a[])
{
    // Sort in descending order
    Arrays.sort(a , Collections.reverseOrder());
 
    int minTime = 0;
 
    // Iterate through the groups
    for (int i = 0; i < n; i += k)
 
        // Update the time taken for each group
        minTime += (2 * a[i]);
 
    // Return the total time taken
    return minTime;
}
 
// Driver code
public static void main(String args[])
{
    int k = 2;
    Integer arr[] = { 2, 3, 4 };
    int n = arr.length;
    System.out.println(minTime(n, k, arr));
}
}
 
// This code is contributed by Pushpesh Raj.

# Python3 implementation of the approach
 
# Function to return the minimum time taken
# by the elevator when operating optimally
def minTime(n, k, a) :
     
    # Sort in descending order
    a.sort(reverse = True);
     
    minTime = 0;
 
    # Iterate through the groups
    for i in range(0, n, k) :
 
        # Update the time taken for
        # each group
        minTime += (2 * a[i]);
 
    # Return the total time taken
    return minTime;
 
# Driver code
if __name__ == "__main__" :
     
    k = 2;
    arr = [ 2, 3, 4 ];
    n = len(arr) ;
    print(minTime(n, k, arr));
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the minimum time taken
// by the elevator when operating optimally
static int minTime(int n, int k, int []a)
{
    // Sort in descending order
    int temp;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            if(a[i] < a[j])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
 
 
    int minTime = 0;
 
    // Iterate through the groups
    for (int i = 0; i < n; i += k)
 
        // Update the time taken for each group
        minTime += (2 * a[i]);
 
    // Return the total time taken
    return minTime;
}
 
// Driver code
public static void Main(String []args)
{
    int k = 2;
    int []arr = { 2, 3, 4 };
    int n = arr.Length;
    Console.Write(minTime(n, k, arr));
}
}
 
// This code is contributed by Arnab Kundu

<script>
 
// JavaScript implementation of the approach
 
// Function to return the minimum time taken
// by the elevator when operating optimally
function minTime(n , k , a)
{
    // Sort in descending order
    var temp;
    for(var i = 0; i < n; i++)
    {    
        for(var j = i + 1; j < n; j++)
        {
            if(a[i] < a[j])
            {
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }   var minTime = 0;
 
    // Iterate through the groups
    for (var i = 0; i < n; i += k)
 
        // Update the time taken for each group
        minTime += (2 * a[i]);
 
    // Return the total time taken
    return minTime;
}
 
// Driver code
var k = 2;
var arr = [ 2, 3, 4 ];
var n = arr.length;
document.write(minTime(n, k, arr));
 
// This code is contributed by Amit Katiyar
 
</script>

12

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(1)