1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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))
|