🧠💡 Java - A More Meaningful Solution - Min Heap of Mechanic Groups Sorted By Least Next Cost
IntuitionWe want to sort and choose mechanics (to take on a next car) by the-minimum total cost to repair their existing cars plus the next car-. This lets us k
# Intuition

We want to sort and choose mechanics (to take on a next car) by the **-minimum total cost to repair their existing cars plus the next car-**. This lets us keep the total time at a minimum **at all times** as we assign each car. We can calculate this cost, which means we can sort by it. To keep the code readable, we'll create a `MechanicGroup` class and encapsulate this total time to repair the next car in our `MechanicGroup` class. We'll also need to track the total time to repair current cars, so we can find our maximum (though we can keep a running maximum).

Also, there are at most 100 distinct ranks, so instead of tracking individual mechanics, we could track groups of mechanics of the same rank and potentially save a lot of time.

So, there are two key ideas:
* Group mechanics by rank, since there are only 100 ranks but up to 100,000 mechanics.
* For each group of mechanics, track how much time it would take them to repair their current assignment of cars **-and-** the assignment of one more car, so we can use this to select the next mechanic group to which to assign more cars to repair.

# Approach

We create a `MechanicGroup` class to encapsulate a group of mechanics of the same rank.  Its fields are:
 * `rank`: the rank of the mechanics
 * `count`: the number of mechanics with this rank
 * `costOfNextCarIncrement`: the amount by which to increment the cost of the next car each time another car is added; equal to twice the rank
 * `repairing`: the number of cars the mechanics are currently repairing
   * this is not actually needed, but may be helpful for debugging; you can omit it for speed
* `time`: the time to repair the current number of cars (`repairing`) being repaired
* `costOfNextCar`: the amount of additional time it would take to repair one more car (per mechanic in this group)
* `timeWithNextCar`: the total amount of time it would take to repair one more car (per mechanic in this group), equivalent to `time + costOfNextCar`

Then we make `MechanicGroup` implement `Comparable<MechanicGroup>` with a sort order based on `timeWithNextCar` ascending. This ensures when we keep our mechanic (groups) in a `PriorityQueue<MechanicGroup>` then the first mechanic group polled is the one that has the least total time if we add another car for each to repair.

We can also prove that the first mechanic group polled has the maximum time once we assign it another car per mechanic. It is obvious that this is true when no cars have yet been repaired, as the mechanic group selected will take time > 0, and all others will have taken time 0. This is the zero case for induction. If you'd like to see the rest of the proof by induction, see below.

And so, we can poll our mechanic groups one at a time, and add a car to them (updating all of the time totals); then we remove their count from the total number of cars needing repair (as the group is taking on as many cars as there are mechanics in the group), continuing until the remaining count is no longer greater than zero. If we go negative, it's okay, it just means that some mechanics within the last group don't actually get an additional car to repair, but at least one does, so the maximum time is potentially impacted.

# Code (Java)
``` java []
class Solution {

    public long repairCars(int[] ranks, int cars) {
        // Group mechanics by rank (max 100 distinct ranks):
        final Map<Integer, Integer> rankFreqMap = new HashMap<>();
        for (int rank : ranks) {
            rankFreqMap.compute(rank, (k, v) -> (v == null ? 1 : v + 1));
        }
        final PriorityQueue<MechanicGroup> pq = new PriorityQueue<>();
        for (Map.Entry<Integer, Integer> rankFreqEntry : rankFreqMap.entrySet()) {
            pq.offer(new MechanicGroup(rankFreqEntry.getKey(), rankFreqEntry.getValue()));
        }
        long maxTime = 0;
        int remaining = cars;
        while (remaining > 0) {
            final MechanicGroup mechanicGroup = pq.poll();
            mechanicGroup.addCarPerMechanic();
            // We do not need Math.max(maxTime, mechanicGroup.getTime()).
            // See proof by induction, below.
            maxTime = mechanicGroup.getTime();
            remaining -= mechanicGroup.getCount();
            pq.offer(mechanicGroup);
        }
        return maxTime;
    }

    static class MechanicGroup implements Comparable<MechanicGroup> {

        final int rank;
        final int count;
        final long costOfNextCarIncrement;
        private int repairing;
        private long time;
        private long costOfNextCar;
        private long timeWithNextCar;

        public MechanicGroup(int rank, int count) {
            this.rank = rank;
            this.count = count;
            this.costOfNextCarIncrement = (rank << 1);
            this.repairing = 0;
            this.time = 0;
            this.costOfNextCar = rank;
            this.timeWithNextCar = rank;
        }

        public int getCount() {
            return this.count;
        }

        public long getTime() {
            return this.time;
        }

        public void addCarPerMechanic() {
            this.repairing++;
            this.time = timeWithNextCar;
            this.costOfNextCar += this.costOfNextCarIncrement;
            this.timeWithNextCar = this.time + this.costOfNextCar;
        }

        @Override
        public int compareTo(final MechanicGroup other) {
            return Long.compare(this.timeWithNextCar, other.timeWithNextCar);
        }
    }
}
```

# Complexity
- Time complexity: This is complicated. We have at most 100 mechanic groups. Let's talk about average time complexity for a large number of mechanic ranks. If we have N cars and M ranks of which R ranks are distinct we'll have an average of M/R mechanics per group, and our loop will run (N/(M/R)) or RN/M times.  Each time it runs, we poll and requeue one mechanic group, which are O(log R) operations, and we do this RN/M times.  So we have a time complexity of O(RN/M log R).  We know R has an upper bound of 100, and if we consider this a constant for R, we really have an O(N/M) time complexity.  (I think - please chime in in the comments if you have a better analysis, I'll be happy to fix this if I'm making things more complex than necessary).

- Space complexity: We need at most R mechanics, so O(R) space, where R is the number of distinct mechanic ranks. If we consider R a constant (max 100) then O(1) space.

# Runtime
110ms as of 2025-02-21. May run faster with removal of the count of cars being repaired (the `repairing` field).

# Why This Solution Matters
A binary search approach (as given in the hint) will work. And it will probably be faster. But in the end, you only have the answer; you do not have the number of cars repaired by each mechanic, nor do you see the solution evolve with each mechanic group taking on additional repairs over time. As a result, a solution like this sets you up to better handle certain obvious follow-up questions, like "in your solution, how many cars do the best-ranked mechanics repair versus the worst-ranked mechanics" and so on. There's nothing wrong with the binary search solution, but this solution gives you more information which is immediately available alongside the answer when it completes.

# Standard Plea
If you found this useful, interesting, or worth a read, **I'd appreciate your upvote**. Even if not, I'd **greatly appreciate any comments to help me write better solutions** (in general, or specific comments on how to improve this one). Thanks for your time and happy coding!

--

# *Proof by Induction Mentioned in the Approach
Above, we claimed that the last mechanic group polled from the queue to take on the last group of cars to repair would have the maximum total time. We will prove this by induction.

Our induction variable `n` will be how many times we have previously polled and assigned cars to a mechanic group. Recall that the PMI states that a hypothesis parameterized by some value `n` may be proven for all non-negative integers `n` if it is proven for `n = 0`, and if when it is assumed for some `n = k`, we can prove it for `n = k + 1`. Our statement then is "When we have previously polled n mechanic groups from our queue and added cars for them to repair, then each previous time and the next time we poll a mechanic group from the queue and add cars for them to repair, their total repair time is the maximum we have encountered so far".

First, note that when we have previously polled 0 mechanic groups, that all groups will have spent 0 time repairing, and whichever group we now poll will spend a non-zero amount of time repairing the cars we add, and thus will have the maximum total repair time. There were no previous times we polled, so the statement holds for n=0.

Now, assume we have previously polled k mechanic groups and each time we did so, the group we polled had the maximum repair time after we added one car per mechanic for them to repair, and that the next group we poll has the maximum repair time after we add one car per mechanic for that group.

This means we have now polled k+1 times where each group had the maximum time, but what about the next group we poll? Let's call that group x (it's the k+2nd group we polled). Now, suppose there is some other group y which has a longer total time. When we polled y, but had not yet added cars, it must have had the shortest of all the total times of all groups in the queue were those groups to repair another batch of cars. And yet, when we added cars to group y, and later polled and added cars to group x, x had a shorter total time. This means when we last polled group y, we should have polled group x instead, because group x had a shorter total time after adding cars to it. This is a contradiction, which means there is no such group y with a longer total time after we have added cars to group x. And thus x, that k+2nd group polled, has the longest total time after polling it and adding a batch of cars for it to repair. This proves that if we assume the hypothesis for `n = k`, we can prove it for `n = k + 1`.

By induction we have proven that each time we poll from our queue (sorted by the minimum total repair time each would have after adding a batch of cars), and add a batch of cars to repair, that group now has the longest total repair time of all groups.

--
#### Edits
2023-03-21: variable name improvements for clarity.
2025-02-21: small performance improvements, re-titled.

['Math', 'Sorting', 'Heap (Priority Queue)', 'Java']