给你一个下标从 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 ，任意顺序下交易都可以全部完成。思路
我只能想到对数组进行排序，但是不知道如何排序，只是想着先按cost进行递减排序，如果cost相等，再按cashback递增排序。但是写出来答案不对。提示的思路是将原数组分为cost>cashback和cost<=cashback两个数组，然后分别排序，如果是赚钱的，则按照cost递减排序；如果是亏钱的，则按照cashback递增排序。
还有一个更好的解法——贪心：
题目要求要以任意一种交易顺序都能完成交易，那就是找出最坏情况下的交易顺序，计算这种交易顺序下需要多少初始金额
贪心的策略：
先进行亏钱的交易，最后一笔亏钱的交易是callback最大的；也就是亏钱交易中callback最大的
先进行亏钱的交易，再进行一笔成本最高的赚钱交易；也就是找出赚钱交易中cost最大的
（1）（2）中选成本最大的
代码
class Solution {
public long minimumMoney(int[][] transactions) {
// Arrays.sort(transactions, (t1, t2)-> {
// //排序，将cost从大到小排，payback从小到大排序
// if (t1[0] == t2[0]) {
// return t1[1]-t2[1];
// } else {
// return t2[0]-t1[0];
// }
// });
List<int[]> cgtb=new ArrayList<>();
List<int[]> cleb=new ArrayList<>();
for (int[] t:transactions) {
if (t[0] > t[1]) {
cgtb.add(t);
} else {
cleb.add(t);
}
}
Collections.sort(cgtb, (t1, t2)->{
return t1[1]-t2[1];
});
Collections.sort(cleb, (t1, t2)-> {
return t2[0]-t1[0];
});
long ans=0;
long cur=0;
for (int[] t : cgtb) {
cur += t[0];
ans = Math.max(cur, ans);
cur -= t[1];
}
for (int[] t : cleb) {
cur += t[0];
ans = Math.max(cur, ans);
cur -= t[1];
}
return ans;
}
}//贪心
class Solution {
public long minimumMoney(int[][] transactions) {
int maxCashBack = 0;
int maxCost = 0;
long sum = 0;
for (int[] transaction : transactions) {
int cost = transaction[0];
int cashBack = transaction[1];
if (cost > cashBack) {
sum += cost - cashBack;
maxCashBack = Math.max(maxCashBack, cashBack);
} else {
maxCost = Math.max(maxCost, cost);
}
}
long ans = sum + Math.max(maxCost, maxCashBack);
return ans;
}
}