目标
给你一个下标从 0 开始的二维整数数组 transactions，其中transactions[i] = [costi, cashbacki] 。
数组描述了若干笔交易。其中每笔交易必须以 某种顺序 恰好完成一次。在任意一个时刻，你有一定数目的钱 money ，为了完成交易 i ，money >= costi 这个条件必须为真。执行交易后，你的钱数 money 变成 money - costi + cashbacki 。
请你返回 任意一种 交易顺序下，你都能完成所有交易的最少钱数 money 是多少。
示例 1：
输入：transactions = [[2,1],[5,0],[4,2]]
输出：10
解释：
刚开始 money = 10 ，交易可以以任意顺序进行。
可以证明如果 money < 10 ，那么某些交易无法进行。示例 2：
输入：transactions = [[3,0],[0,3]]
输出：3
解释：
- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。
- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。
所以，刚开始钱数为 3 ，任意顺序下交易都可以全部完成。说明：
- 1 <= transactions.length <= 10^5
- transactions[i].length == 2
- 0 <= costi, cashbacki <= 10^9
提示：
- Split transactions that have cashback greater or equal to cost apart from transactions that have cashback less than cost. You will always earn money in the first scenario.
- For transactions that have cashback greater or equal to cost, sort them by cost in descending order.
- For transactions that have cashback less than cost, sort them by cashback in ascending order.
思路
有若干笔交易 transactions，transactions[i] = [costi, cashbacki] 表示每笔交易的现金支出为 costi，收入为 cashbacki。求以任意顺序完成交易所需的最少现金 money，完成交易 i 需要满足 money >= costi。
注意题目求的是任意顺序下都能完成所有交易的最少现金数量，而不是求所有交易顺序中，能够保证完成所有交易的现金最小值。
看了提示，说是任意顺序，其实就是求启动资金的最大值。总的思路是这样的：
- 先赔后赚，将交易划分成两部分，一部分赔钱一部分赚钱
- 对于赔钱的交易，优先按回款从小到大排序，这样为了完成所有交易所需的钱最多
- 对于赚钱的交易，按支出顺序从大到小排序，只要能完成最大支出的交易，那么后续交易也一定能完成
代码
/**
* @date 2025-01-25 20:42
*/
public class MinimumMoney2412 {
public long minimumMoney(int[][] transactions) {
Arrays.sort(transactions, (a, b) -> {
int diffa = a[1] - a[0];
int diffb = b[1] - b[0];
return diffa - diffb;
});
int cut = 0;
for (int[] transaction : transactions) {
if (transaction[0] <= transaction[1]) {
break;
}
cut++;
}
int n = transactions.length;
int[][] a = new int[cut][];
int[][] b = new int[n - cut][];
System.arraycopy(transactions, 0, a, 0, cut);
System.arraycopy(transactions, cut, b, 0, n - cut);
Arrays.sort(a, (x, y) -> x[1] - y[1]);
Arrays.sort(b, (x, y) -> y[0] - x[0]);
long res = 0;
long remainder = 0;
for (int[] item : a) {
if (remainder < item[0]) {
res += item[0] - remainder;
}
remainder = item[1];
}
if (b.length > 0 && remainder < b[0][0]) {
res += b[0][0] - remainder;
}
return res;
}
}
性能
