2594. Minimum Time to Repair Cars

Problem

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.

Example 1:

Input: ranks = [4,2,3,1], cars = 10
Output: 16
Explanation:
- The first mechanic will repair two cars. The time required is 4 * 2 * 2 = 16 minutes.
- The second mechanic will repair two cars. The time required is 2 * 2 * 2 = 8 minutes.
- The third mechanic will repair two cars. The time required is 3 * 2 * 2 = 12 minutes.
- The fourth mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Example 2:

Input: ranks = [5,1,8], cars = 6
Output: 16
Explanation:
- The first mechanic will repair one car. The time required is 5 * 1 * 1 = 5 minutes.
- The second mechanic will repair four cars. The time required is 1 * 4 * 4 = 16 minutes.
- The third mechanic will repair one car. The time required is 8 * 1 * 1 = 8 minutes.
It can be proved that the cars cannot be repaired in less than 16 minutes.​​​​​

Constraints:

• 1 <= ranks.length <= 105
• 1 <= ranks[i] <= 100
• 1 <= cars <= 106

Solution (Java)

class Solution {
    public long repairCars(int[] arr, int c) {
        long[] ranks = new long[arr.length];
        int idx = 0;
        for(int ele : arr)
        {
            ranks[idx++] = (ele * 1l);
        }
        Arrays.sort(ranks);
        long cars = (c * 1l);

        int n = ranks.length;
        long time = (int)1e14;
        long si = 0;
        long ei = Long.MAX_VALUE;

        while(si <= ei)
        {
            long mid = (si) + (ei - si)/2;
            if(helper(mid, ranks, cars))
            {
                time = mid;
                ei = mid - 1;
            }
            else
            {
                si = mid + 1;
            }
        }
        return time;
    }

    public boolean helper(long mid, long[] ranks, long cars)
    {
        for(int i = 0; i < ranks.length; i++)
        {
            long x = (long)Math.floor(Math.sqrt((mid * 1.0)/(ranks[i] * 1.0)));
            if(x >= cars)
                return true;
            cars-= x;
            if(cars == 0)
                return true;
        }
        return (cars == 0);
    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).