diff options
author | Jack Sangdahl <[email protected]> | 2025-03-15 18:13:16 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-15 18:13:16 -0600 |
commit | a1df0fb34031b85f24094bec64c7660db4479483 (patch) | |
tree | 5d7cace02a893a8248e0b5e813f15d60370a54ae /min_time_repair_car.py | |
parent | 5e923e65f2bef08dd917ca1cf9581a7a60bab8c9 (diff) | |
download | leetcode-a1df0fb34031b85f24094bec64c7660db4479483.tar.gz leetcode-a1df0fb34031b85f24094bec64c7660db4479483.zip |
2594. minimum time to repair cars
Diffstat (limited to 'min_time_repair_car.py')
-rw-r--r-- | min_time_repair_car.py | 36 |
1 files changed, 36 insertions, 0 deletions
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)) |