diff options
-rw-r--r-- | min_time_repair_car.c | 31 | ||||
-rw-r--r-- | min_time_repair_car.py | 36 |
2 files changed, 67 insertions, 0 deletions
diff --git a/min_time_repair_car.c b/min_time_repair_car.c new file mode 100644 index 0000000..ddd9dce --- /dev/null +++ b/min_time_repair_car.c @@ -0,0 +1,31 @@ +// 2594. Minimum Time to Repair Cars +#include "leetcode.h" + +/* + * you are given an integer array 'ranks' representing the ranks of some + * mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a + * rank 'r' can repair 'n' cars in 'r * n^2' minutes. you are also given an + * integer 'cars' representing the total number of cars waiting in the garage to + * be repaired. return the minimum time taken to repair all the cars. note: all + * the mechanics can repair the cars simultaneously. + */ + +long long repairCars(int *ranks, int ranksSize, int cars) { + long long left = 0, right = 1e14; + while (left < right) { + long long mid = left + (right - left) / 2, cnt = 0; + for (int i = 0; i < ranksSize; i++) + cnt += sqrt(mid / ranks[i]); + if (cnt < cars) + left = mid + 1; + else + right = mid; + } + return left; +} + +int main() { + int r1[] = {4, 2, 3, 1}, r2[] = {5, 1, 8}; + printf("%lld\n", repairCars(r1, ARRAY_SIZE(r1), 10)); // expect: 16 + printf("%lld\n", repairCars(r2, ARRAY_SIZE(r2), 6)); // expect: 16 +} diff --git a/min_time_repair_car.py b/min_time_repair_car.py new file mode 100644 index 0000000..7f8db29 --- /dev/null +++ b/min_time_repair_car.py @@ -0,0 +1,36 @@ +# 2594. Minimum Time to Repair Cars +import heapq +from collections import Counter + +""" +you are given an integer array 'ranks' representing the ranks of some +mechanics. 'ranks[i]' is the rank of the i'th mechanic. a mechanic with a +rank 'r' can repair 'n' cars in 'r n^2' minutes. you are also given an +integer 'cars' representing the total number of cars waiting in the garage to +be repaired. return the minimum time taken to repair all the cars. note: all +the mechanics can repair the cars simultaneously. +""" + + +class Solution(object): + def repairCars(self, ranks, cars): + """ + :type ranks: List[int] + :type cars: int + :rtype: int + """ + cnt = Counter(ranks) + h = [[i, i, 1, cnt[i]] for i in cnt] + heapq.heapify(h) + while cars > 0: + time, rank, k, count = heapq.heappop(h) + cars -= count + k += 1 + heapq.heappush(h, [rank * k * k, rank, k, count]) + return time + + +if __name__ == "__main__": + obj = Solution() + print(obj.repairCars(ranks=[4, 2, 3, 1], cars=10)) + print(obj.repairCars(ranks=[5, 1, 8], cars=6)) |