2594: Minimum-Time-to-Repair-Cars
Medium
Similar to yesterday and the day before yesterday, it is just a binary search problem, where you binary search the maximum time taken by a mechanic.
Code:
class Solution {
public:
long long repairCars(vector<int>& ranks, int cars) {
long long left = 0;
long long right = ranks[0] * (long long)cars * (long long)cars;
long long ans = 0;
while (left <= right) {
long long mid = left - (left - right)/2;
long long counter = 0;
for (int i = 0; i < ranks.size() && counter < cars; ++i) {
counter += sqrt(mid/ranks[i]);
}
if (counter >= cars) {
ans = mid;
right = mid-1;
} else {
left = mid+1;
}
}
return ans;
}
};Complexity:
We can technically speed up the time
complexity, by precomputing a rank_count
array of size 100. This means we do not have to
iterate through the entirety of
ranks and only need to iterate through a maximum of
100 values.
Code:
class Solution {
public:
long long repairCars(vector<int>& ranks, int cars) {
int ranksCount[101] = {0};
int minRank = 101;
int maxRank = 0;
for (int rank : ranks) {
minRank = min(minRank, rank);
maxRank = max(maxRank, rank);
++ranksCount[rank];
}
long long left = 0;
long long right = minRank * (long long)cars * (long long)cars;
long long ans = 0;
while (left <= right) {
long long mid = left - (left - right)/2;
long long counter = 0;
for (int i = minRank; i <= maxRank; ++i) {
counter += ranksCount[i] * (long long)(sqrt(mid/i));
if (counter >= cars) break;
}
if (counter >= cars) {
ans = mid;
right = mid-1;
} else {
left = mid+1;
}
}
return ans;
}
};