Given m roads and n cars. The cars are numbered from 1 to n. You are also given an array arr[] of size m, each road has a value arr[i] – the index of a car that runs fast on this road. If a car is fast on a road, then it travels across the road in 1 hour, else it takes 2 hours (if not proficient) to travel through this road. Find out the minimum time required by these n cars to travel through all of these m roads.
All cars run independently of each other and each car can run on a single road at once. All roads have the same length.
Examples:
Input: N = 2, M = 4, arr[] = {1, 2, 1, 2}
Output: 2
Explanation: The first car will run on the 1st and 3rd roads and the Second car will be running on the 2nd and 4th roads. Both cars completed 2 roads in 2 hours as both are proficient in traveling their corresponding roads.Input: N = 2, M = 4, arr[] = {1, 1, 1, 1}
Output: 3
Explanation: The first car will run on the 1st, 2nd, and 3rd roads, whereas the 4th road will be assigned to the 2nd car. The first car will be finishing his road in 3 hours, whereas the second car spends 2 hours (as the 2nd car is not proficient in traveling the 4th road).
Approach: The problem can be solved based on the following observation.
If you can use the cars in such a way that all roads can be traveled in time x, Then, you can complete all these roads using x + 1 or more time as well.
Follow the steps mentioned below to implement the idea:
- As we are binary searching for the answer, we have to define the upper bound.
- In the Worst case, the total time can be 2 * m hours to travel through all roads. For example: if you assign all roads to a single car, and this car is not proficient in any of these roads.
- To check whether all roads can be completed in the given time we will be creating a lambda function.
- The function will be keeping track of free roads and needed roads.
- If the given time is greater than the total roads assigned to a car.
- Add the extra time to the free roads slot.
- Else, Add the left roads to the needed road.
- In the end, if needed roads are greater than the free roads slot, Thus it is not possible to complete all of the roads in the given time amount.
Below is the Implementation of the above approach:
C++
// C++ code of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calcuate minimum
// time required
void minTimeRequired(int n, int m, vector<int> arr)
{
// cnt to count the total number of
// road the ith car is proficient in
vector<int> cnt(n + 1);
// Calculating the total no. of
// proficient roads that each
// car can do
for (int i = 0; i < m; i++)
cnt[arr[i]]++;
// Lambda function to check weather
// given time is enough to complete
// all m roads using n cars
auto check = [&](int time) {
long long free = 0, needed = 0;
for (int i = 1; i <= n; i++) {
if (time >= cnt[i]) {
// Storing the number of
// roads that can be done
// if the provided time is
// more than the number of
// efficient roads assigned
// to a car
long long extraTime = (time - cnt[i]);
// We are dividing the
// difference by 2 because
// as it is mentioned in the
// question if the car is
// not proficient then 2
// sec are required to
// complete a road.
free += extraTime / 2;
}
else {
// Storing the number of
// roads that are left
needed += cnt[i] - time;
}
}
// If free road slots are greater
// than or equal to the needed,
// then it is possible to complete
// all m roads in the given time
return needed <= free;
};
// Maximum required time in worst
// case is 2*m, if you assign all
// roads to a single car, and this car
// is not proficient in any of
// these roads.
int l = 0, r = 2 * m;
int minTime = -1;
// Binary Search on minTime
while (l <= r) {
int m = (l + r) / 2;
if (check(m)) {
// If we are able to complete
// all roads using m unit of
// time then check with lesser
// time again
minTime = m;
r = m - 1;
}
else {
l = m + 1;
}
}
cout << minTime << '\n';
}
// Driver Code
int main()
{
int n = 2, m = 4;
vector<int> arr(m);
arr = { 1, 2, 1, 2 };
// Function call
minTimeRequired(n, m, arr);
return 0;
}
Time Complexity: O(n*logm)
Auxiliary Space: O(n)
Related Articles: