Thursday, February 9, 2023
HomeSoftware DevelopmentMinimal time required by n vehicles to journey via all the m...

Minimal time required by n vehicles to journey via all the m roads


Given m roads and n vehicles. The vehicles are numbered from 1 to n. You might be additionally given an array arr[] of dimension m, every street has a price arr[i] – the index of a automobile that runs quick on this street. If a automobile is quick on a street, then it travels throughout the street in 1 hour, else it takes 2 hours (if not proficient) to journey via this street. Discover out the minimal time required by these n vehicles to journey via all of those m roads. 

All vehicles run independently of one another and every automobile can run on a single street without delay. All roads have the identical size. 

Examples: 

Enter:  N = 2, M = 4, arr[] = {1, 2, 1, 2}
Output: 2
Clarification: The primary automobile will run on the first and third roads and the Second automobile will probably be operating on the 2nd and 4th roads. Each vehicles accomplished 2 roads in 2 hours as each are proficient in touring their corresponding roads.

Enter: N = 2, M = 4, arr[] = {1, 1, 1, 1}
Output: 3
Clarification: The primary automobile will run on the first, 2nd, and third roads, whereas the 4th street will probably be assigned to the 2nd automobile. The primary automobile will probably be ending his street in 3 hours, whereas the second automobile spends 2 hours (because the 2nd automobile will not be proficient in touring the 4th street).

Method: The issue will be solved based mostly on the next statement.

If you should utilize the vehicles in such a method that each one roads will be traveled in time x, Then, you possibly can full all these roads utilizing x + 1 or extra time as nicely.

Observe the steps talked about beneath to implement the concept:

  • As we’re binary looking for the reply, we have now to outline the higher sure. 
  • Within the Worst case, the whole time will be 2 * m hours to journey via all roads. For instance: if you assign all roads to a single automobile, and this automobile will not be proficient in any of those roads.
  • To examine whether or not all roads will be accomplished within the given time we will probably be making a lambda operate.
  • The operate will probably be retaining monitor of free roads and wanted roads. 
  • If the given time is bigger than the whole roads assigned to a automobile.
    • Add the additional time to the free roads slot.
  • Else, Add the left roads to the wanted street.
  • Ultimately, if wanted roads are larger than the free roads slot, Thus it isn’t attainable to finish all the roads within the given time quantity.

Under is the Implementation of the above method:

C++

// C++ code of the above method
#embody <bits/stdc++.h>
utilizing namespace std;

// Operate to calcuate minimal
// time required
void minTimeRequired(int n, int m, vector<int> arr)
{

    // cnt to rely the whole variety of
    // street the ith automobile is proficient in
    vector<int> cnt(n + 1);

    // Calculating the whole no. of
    // proficient roads that every
    // automobile can do
    for (int i = 0; i < m; i++)

        cnt[arr[i]]++;

    // Lambda operate to examine climate
    // given time is sufficient to full
    // all m roads utilizing n vehicles
    auto examine = [&](int time) {
        lengthy lengthy free = 0, wanted = 0;

        for (int i = 1; i <= n; i++) {
            if (time >= cnt[i]) {

                // Storing the variety of
                // roads that may be achieved
                // if the offered time is
                // greater than the variety of
                // environment friendly roads assigned
                // to a automobile
                lengthy lengthy extraTime = (time - cnt[i]);

                // We're dividing the
                // distinction by 2 as a result of
                // as it's talked about within the
                // query if the automobile is
                // not proficient then 2
                // sec are required to
                // full a street.
                free += extraTime / 2;
            }
            else {

                // Storing the variety of
                // roads which can be left
                wanted += cnt[i] - time;
            }
        }

        // If free street slots are larger
        // than or equal to the wanted,
        // then it's attainable to finish
        // all m roads within the given time

        return wanted <= free;
    };

    // Most required time in worst
    // case is 2*m, if you happen to assign all
    // roads to a single automobile, and this automobile
    // will not be proficient in any of
    // these roads.
    int l = 0, r = 2 * m;
    int minTime = -1;

    // Binary Search on minTime
    whereas (l <= r) {

        int m = (l + r) / 2;
        if (examine(m)) {

            // If we're capable of full
            // all roads utilizing m unit of
            // time then examine with lesser
            // time once more
            minTime = m;

            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }

    cout << minTime << 'n';
}

// Driver Code
int essential()
{
    int n = 2, m = 4;
    vector<int> arr(m);
    arr = { 1, 2, 1, 2 };

    // Operate name
    minTimeRequired(n, m, arr);

    return 0;
}

Time Complexity: O(n*logm)
Auxiliary House: O(n)

Associated Articles:

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments