Минимальное время, необходимое для транспортировки всех ящиков от источника до места назначения при заданных ограничениях

Опубликовано: 13 Января, 2022

Даны два массива: box [] и truck [], где box [i] представляет вес i- го контейнера, а truck [i] представляет максимальную нагрузку, которую может нести i- й грузовик. Теперь каждому грузовику требуется 1 час, чтобы перевезти коробку из пункта отправления в пункт назначения, и еще один час, чтобы вернуться обратно . Теперь, учитывая, что все ящики хранятся у источника, задача состоит в том, чтобы найти минимальное время, необходимое для транспортировки всех ящиков от источника к месту назначения.

Обратите внимание, что всегда будет какое-то время, в течение которого коробки можно будет транспортировать, и только один ящик может быть перевезен грузовиком в любой момент времени.

Примеры:

Input: box[] = {7, 6, 5, 4, 3}, truck[] = {10, 3} 
Output:
1st hour: truck[0] carries box[0] and truck[1] carries box[4] 
2nd hour: Both trucks are back at the source location. 
Now, truck[1] cannot carry anymore boxes as all the remaining boxes 
have weights more than the capacity of a truck[1]. 
So, truck[0] will carry box[1] and box[2] 
in a total of four hours. (source-destination and then destination-source) 
And finally, box[3] will take another hour to reach the destination. 
So, total time taken = 2 + 4 + 1 = 7

Input: box[] = {10, 2, 16, 19}, truck[] = {29, 25} 
Output: 3  

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать двоичный поиск и отсортировать два массива. Здесь нижняя граница будет равна 0, а верхняя граница будет 2 * размер box [], потому что в худшем случае количество времени, необходимое для транспортировки всех ящиков, будет 2 * размера массива ящиков. Теперь вычислите среднее значение и для каждого среднего значения проверьте, все ли коробки могут быть перевезены загрузчиками за time = mid. Если да, то обновите верхнюю границу как mid - 1, а если нет, то обновите нижнюю границу как mid + 1 .

Below is the implementation of the above approach:  

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
bool isPossible(int box[], int truck[],
                int n, int m, int min_time)
{
    int temp = 0;
    int count = 0;
 
    while (count < m) {
        for (int j = 0; j < min_time
                        && temp < n
                        && truck[count] >= box[temp];
             j += 2)
            temp++;
 
        count++;
    }
 
    // If all the boxes can be
    // transported in the given time
    if (temp == n)
        return true;
 
    // If all the boxes can"t be
    // transported in the given time
    return false;
}
 
// Function to return the minimum time required
int minTime(int box[], int truck[], int n, int m)
{
 
    // Sort the two arrays
    sort(box, box + n);
    sort(truck, truck + m);
 
    int l = 0;
    int h = 2 * n;
 
    // Stores minimum time in which
    // all the boxes can be transported
    int min_time = 0;
 
    // Check for the minimum time in which
    // all the boxes can be transported
    while (l <= h) {
        int mid = (l + h) / 2;
 
        // If it is possible to transport all
        // the boxes in mid amount of time
        if (isPossible(box, truck, n, m, mid)) {
            min_time = mid;
            h = mid - 1;
        }
        else
            l = mid + 1;
    }
 
    return min_time;
}
 
// Driver code
int main()
{
    int box[] = { 10, 2, 16, 19 };
    int truck[] = { 29, 25 };
 
    int n = sizeof(box) / sizeof(int);
    int m = sizeof(truck) / sizeof(int);
 
    printf("%d", minTime(box, truck, n, m));
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.Arrays;
 
class GFG
{
 
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
static boolean isPossible(int box[], int truck[],
                int n, int m, int min_time)
{
    int temp = 0;
    int count = 0;
 
    while (count < m)
    {
        for (int j = 0; j < min_time
                        && temp < n
                        && truck[count] >= box[temp];
            j += 2)
            temp++;
 
        count++;
    }
 
    // If all the boxes can be
    // transported in the given time
    if (temp == n)
        return true;
 
    // If all the boxes can"t be
    // transported in the given time
    return false;
}
 
// Function to return the minimum time required
static int minTime(int box[], int truck[], int n, int m)
{
 
    // Sort the two arrays
    Arrays.sort(box);
    Arrays.sort(truck);
 
    int l = 0;
    int h = 2 * n;
 
    // Stores minimum time in which
    // all the boxes can be transported
    int min_time = 0;
 
    // Check for the minimum time in which
    // all the boxes can be transported
    while (l <= h) {
        int mid = (l + h) / 2;
 
        // If it is possible to transport all
        // the boxes in mid amount of time
        if (isPossible(box, truck, n, m, mid))
        {
            min_time = mid;
            h = mid - 1;
        }
        else
            l = mid + 1;
    }
 
    return min_time;
}
 
// Driver code
public static void main(String[] args)
{
    int box[] = { 10, 2, 16, 19 };
    int truck[] = { 29, 25 };
 
    int n = box.length;
    int m = truck.length;
 
    System.out.printf("%d", minTime(box, truck, n, m));
}
}
 
/* This code contributed by PrinciRaj1992 */

Python3

# Python3 implementation of the approach
 
# Function that returns true if it is
# possible to transport all the boxes
# in the given amount of time
def isPossible(box, truck, n, m, min_time) :
     
    temp = 0
    count = 0
 
    while (count < m) :
        j = 0
        while (j < min_time and temp < n and
                    truck[count] >= box[temp] ):
            temp +=1
            j += 2
 
        count += 1
 
    # If all the boxes can be
    # transported in the given time
    if (temp == n) :
        return True
 
    # If all the boxes can"t be
    # transported in the given time
    return False
 
# Function to return the minimum time required
def minTime(box, truck, n, m) :
 
    # Sort the two arrays
    box.sort();
    truck.sort();
 
    l = 0
    h = 2 * n
 
    # Stores minimum time in which
    # all the boxes can be transported
    min_time = 0
 
    # Check for the minimum time in which
    # all the boxes can be transported
    while (l <= h) :
        mid = (l + h) // 2
 
        # If it is possible to transport all
        # the boxes in mid amount of time
        if (isPossible(box, truck, n, m, mid)) :
            min_time = mid
            h = mid - 1
     
        else :
             
            l = mid + 1
 
    return min_time
 
# Driver code
if __name__ == "__main__" :
 
    box = [ 10, 2, 16, 19 ]
    truck = [ 29, 25 ]
 
    n = len(box)
    m = len(truck)
 
    print(minTime(box, truck, n, m))
     
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
     
class GFG
{
 
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
static bool isPossible(int []box, int []truck,
                int n, int m, int min_time)
{
    int temp = 0;
    int count = 0;
 
    while (count < m)
    {
        for (int j = 0; j < min_time
                        && temp < n
                        && truck[count] >= box[temp];
            j += 2)
            temp++;
 
        count++;
    }
 
    // If all the boxes can be
    // transported in the given time
    if (temp == n)
        return true;
 
    // If all the boxes can"t be
    // transported in the given time
    return false;
}
 
// Function to return the minimum time required
static int minTime(int []box, int []truck, int n, int m)
{
 
    // Sort the two arrays
    Array.Sort(box);
    Array.Sort(truck);
 
    int l = 0;
    int h = 2 * n;
 
    // Stores minimum time in which
    // all the boxes can be transported
    int min_time = 0;
 
    // Check for the minimum time in which
    // all the boxes can be transported
    while (l <= h)
    {
        int mid = (l + h) / 2;
 
        // If it is possible to transport all
        // the boxes in mid amount of time
        if (isPossible(box, truck, n, m, mid))
        {
            min_time = mid;
            h = mid - 1;
        }
        else
            l = mid + 1;
    }
 
    return min_time;
}
 
// Driver code
public static void Main(String[] args)
{
    int[] box = { 10, 2, 16, 19 };
    int []truck = { 29, 25 };
 
    int n = box.Length;
    int m = truck.Length;
 
    Console.WriteLine("{0}", minTime(box, truck, n, m));
}
}
 
/* This code contributed by PrinciRaj1992 */

PHP

<?php
 
// PHP implementation of the approach
 
// Function that returns true if it is
// possible to transport all the boxes
// in the given amount of time
function isPossible($box, $truck,
                $n, $m, $min_time)
{
    $temp = 0;
    $count = 0;
 
    while ($count < $m)
    {
        for ( $j = 0; $j < $min_time
                        && $temp < $n
                        && $truck[$count] >= $box[$temp];
            $j += 2)
            $temp++;
 
        $count++;
    }
 
    // If all the boxes can be
    // transported in the given time
    if ($temp == $n)
        return true;
 
    // If all the boxes can"t be
    // transported in the given time
    return false;
}
 
// Function to return the minimum time required
function minTime( $box, $truck, $n, $m)
{
 
    // Sort the two arrays
    sort($box);
    sort($truck);
 
    $l = 0;
    $h = 2 * $n;
 
    // Stores minimum time in which
    // all the boxes can be transported
    $min_time = 0;
 
    // Check for the minimum time in which
    // all the boxes can be transported
    while ($l <= $h) {
        $mid = intdiv(($l + $h) , 2);
 
        // If it is possible to transport all
        // the boxes in mid amount of time
        if (isPossible($box, $truck, $n, $m, $mid))
        {
            $min_time = $mid;
            $h = $mid - 1;
        }
        else
            $l = $mid + 1;
    }
 
    return $min_time;
}
 
// Driver code

РЕКОМЕНДУЕМЫЕ СТАТЬИ