Leetcode 2594. Minimum Time to Repair Cars

문제

You are given an integer array ranks representing the ranks of some mechanics. ranksi is the rank of the ith mechanic. A mechanic with a rank r can repair n cars in r * n2 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.

문제: 모든 차량 수리 최소 시간 계산

정비공들의 랭크를 나타내는 정수 배열 ranks가 주어집니다. ranks[i]는 i번째 정비공의 랭크입니다. 랭크 r을 가진 정비공은 n대의 차를 수리하는데 r * n² 분이 소요됩니다.

또한 정비소에서 수리를 기다리는 총 차량의 수를 나타내는 정수 cars가 주어집니다.

모든 차량을 수리하는데 걸리는 최소 시간을 반환하세요.

참고: 모든 정비공은 동시에 차량을 수리할 수 있습니다.

---

예시

입력 예시

• ranks = [4,2,3,1]
• cars = 10

출력
16

상세 설명

• 첫 번째 정비공: 2대 수리, 소요 시간 4 * 2² = 16분
• 두 번째 정비공: 2대 수리, 소요 시간 2 * 2² = 8분
• 세 번째 정비공: 2대 수리, 소요 시간 3 * 2² = 12분
• 네 번째 정비공: 4대 수리, 소요 시간 1 * 4² = 16분

---

제한

• $1 <= ranks.length <= 10^5$
• $1 <= ranks[i] <= 100$
• $1 <= cars <= 10^6$

---

풀이

• 이진탐색을 활용한다.
• 정답의 범위를 좁혀 나가는 방식을 사용

class Solution:
    def repairCars(self, ranks: List[int], cars: int) -> int:
        def check(maxima: int) -> bool:
            count = 0
            for rank in ranks:
                m = maxima / rank
                m = floor(m ** 0.5)
                count += m
            return count >= cars

        left = min(ranks)
        right = max(ranks) * (cars ** 2)

        ans = 0

        while left <= right:
            mid = (left + right) // 2

            if check(mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1

        return ans