Sort with Custom Comparator, with Detailed Explanations
Observation 1: If we pick some permutaion and go through the transactions in that order, the amount of money we need at the start = - the lowest our money dippe
Observation 1: If we pick some permutaion and go through the transactions in that order, the amount of money we need at the start = - the lowest our money dipped at any point. Same logic as https://leetcode.com/problems/dungeon-game/\neg if the permutation is [5, 0] [4, 2] [2, 1], then the amount of money at each point in time will be -5, -5, -9, -7, -9, -8\nLowest = -9, so amount of money needed at the start = 9.\n\nSo we have to find the permutation where the money dips the lowest. (ie the worst permutation)\n\nHow do we find the worst permutaton ? One way is to try and establish an ordering between the transactions such that we end up with the worst permuation. Some orderings that come to mind are ordering by the difference between cahsback and cost, ratio between them, etc, but each of those have simple counter examples. \n\nInstead of assigning some value to a transaction like t[1] - t[0] or t[1] / t[0] and sorting by that, we can look at 2 transactions t1 and t2 together and see whether t1 then t2 or t2 then t1 is worse. This can easily be done. Just simulate t1 then t2 and t2 then t1 and see in which one the money dips lower.\nSo given two transactions a and b, we can tell whether a < b or b < a. For our comparator to be valid, a<b and b<c should imply a<c. This can also easily be verified. Also whether we do t1 then t2 or t2 then t1, the balance remains the same in the end. \n\nNow we simply sort by this comparator and simulate the the transactions in the worst permutation and find the answer.\n\nJava code (a bit messy):\n```\nclass Solution {\n    private static class Transaction implements Comparable<Transaction> {\n        int minus;\n        int plus;\n        Pair(int minus, int plus) {\n            this.minus = minus;\n            this.plus = plus;\n        }\n        \n        @Override\n        public int compareTo(Transaction other) {\n            // this then other\n            int option1 = Math.min(-this.minus, -this.minus + this.plus - other.minus);\n            \n            // other then this\n            int option2 = Math.min(-other.minus, -other.minus + other.plus - this.minus);\n            \n            if(option1 < option2) {\n                return -1;\n            }\n            if(option1 > option2) {\n                return 1;\n            }\n\t\t\t// in case of a tie, order by cost / cashback\n            if(this.minus < other.minus) {\n                return -1;\n            }\n            if(this.minus > other.minus) {\n                return 1;\n            }\n            return this.plus - other.plus;\n        }\n        \n    }\n    \n    public long minimumMoney(int[][] transactions) {\n        List<Transaction> list = new ArrayList<>();\n        \n        for(int[] row : transactions) {\n            list.add(new Transaction(row[0], row[1]));\n        }\n        \n        Collections.sort(list);\n        \n        long res = Integer.MAX_VALUE;\n        long money = 0;\n        for(Transaction t : list) {\n            money -= t.minus;\n            res = Math.min(res, money);\n            money += t.plus;\n        }\n        \n        return -res;\n    }\n}\n```\n\n
['Sorting']