Rearranging Fruits

2023 年 2 月 5 日星期日(已编辑)

/ ,

摘要

The problem involves balancing fruit costs between two baskets. If the total count of any fruit cost is odd, balancing is impossible. Excess fruits are listed and sorted. A greedy strategy pairs smallest and largest costs to minimize exchange costs, choosing between direct or indirect swaps based on cost efficiency. Time complexity is O(n log n) due to sorting.

这篇文章上次修改于 2025 年 8 月 3 日星期日，可能部分内容已经不适用，如有疑问可询问作者。

Question

Approach: Greedy

Intuition

According to the problem, the cost x of any fruit must appear an even number of times across the two fruit baskets; otherwise, it is impossible to evenly distribute the fruit with cost x between the two baskets. To compute the imbalance in fruit costs between the two baskets, we can use two hash tables, $count_1$ and $count_2$ , to count the number of times each fruit cost appears in $basket_1$ and $basket_2$ , respectively. For a given fruit cost $x$ :

If $count_1[x]+count_2[x]$ is odd, we return $−1$ immediately, since balancing is impossible.

If $count_1[x]>count_2[x]$ , then $\frac{count_1[x]−count_2[x]}{2}$ fruits with cost x must be moved from $basket_1$ to $basket_2$ , and vice versa.

Following point 2, we enumerate all such costs $x$ and add each to a list called $merge$ with a count equal to the number of excess fruits that need to be exchanged. We then sort merge in increasing order. According to the greedy strategy, we pair the smallest values from the first half of the list with the largest from the second half to minimize the overall exchange cost. For each pair of costs $x_1$ and $x_2$ $(x_1 < x_2)$ , there are two possible exchange strategies:

Direct exchange: Swap $x_1$ with $x_2$ , with a cost of $x_1$ .

Indirect exchange: Both $x_1$ and $x_2$ are exchanged through the minimum fruit cost m across both baskets, with a total cost of $2×m$ .

We iterate over the first half of the $merge$ list, and for each element $x$ , we accumulate the cost $min(x,2×m)$ into the final result.

Implementation

CodeBlock Loading...

Timing

NULL

Completixy

Time

$O(nlogn)$ , from sorting

Space

$O(n)$

Approach: Greedy

Intuition

count_1

and

count_2

, to count the number of times each fruit cost appears in

basket_1

and

basket_2

, respectively. For a given fruit cost

x

count_1[x]+count_2[x]

is odd, we return

−1

immediately, since balancing is impossible.

count_1[x]>count_2​[x]

, then

\frac{count_1[x]−count_2[x]}{2}

fruits with cost x must be moved from

basket_1

basket_2

, and vice versa.

Following point 2, we enumerate all such costs

x

and add each to a list called

merge

with a count equal to the number of excess fruits that need to be exchanged. We then sort merge in increasing order. According to the greedy strategy, we pair the smallest values from the first half of the list with the largest from the second half to minimize the overall exchange cost. For each pair of costs

x_1

and

x_2

(x_1 < x_2)

, there are two possible exchange strategies:

Direct exchange: Swap

x_1

with

x_2

, with a cost of

x_1

Indirect exchange: Both

x_1

and

x_2

are exchanged through the minimum fruit cost m across both baskets, with a total cost of

2×m

We iterate over the first half of the

merge

list, and for each element

x

, we accumulate the cost

min(x,2×m)

into the final result.

Implementation

class Solution {
    public long minCost(int[] basket1, int[] basket2) {
        TreeMap<Integer, Integer> freq = new TreeMap<>();
        int m = Integer.MAX_VALUE;
        for (int b1 : basket1) {
            freq.put(b1, freq.getOrDefault(b1, 0) + 1);
            m = Math.min(m, b1);
        }
        for (int b2 : basket2) {
            freq.put(b2, freq.getOrDefault(b2, 0) - 1);
            m = Math.min(m, b2);
        }

        List<Integer> merge = new ArrayList<>();
        for (var entry : freq.entrySet()) {
            int count = entry.getValue();
            if (count % 2 != 0) return -1;
            for (int i = 0; i < Math.abs(count) / 2; i++) {
                merge.add(entry.getKey());
            }
        }

        Collections.sort(merge);
        long res = 0;
        for (int i = 0; i < merge.size() / 2; i++) {
            res += Math.min(2 * m, merge.get(i));
        }
        return res;
    }
}

CodeBlock Loading...