[Java] - BST pattern -  same Leetcode problems and Greedy Idea - 100%
Idea 1: BST \n\nHow can we break this issue into a smaller problem? \nThink about this :\n\n What is the minimum potential result can it be ? --> min = sum of a
**Idea 1: BST **\n\nHow can we break this issue into a smaller problem? \nThink about this :\n\n* What is the minimum potential result can it be ? --> min = sum of all task[0]\n* What is the maximum potential result can it be ? --> max = sum of all ( task[0] + task[1] )\n\n If result is a number (X). is X a valid number/result ?\n* \t\t if yes -> can we reduce the number X to make it mininum and still valid ?\n* \t\t if no -> we need to increase X to make it valid.  \n\nThe only small difference compare to other same problems is building the MaxHeap - The biggest task[1] - task[0] will need to be consider first \n\n\n\n\n* Same problems : \n\n\n875\t- Koko Eating Bananas  \n410\t- Split Array Largest Sum  \n1231 - Divide Chocolate\n134 - Gas Station  \n\nHere is a great resource (thanks @aravind_dev): \nhttps://leetcode.com/discuss/general-discussion/691825/Binary-Search-for-Beginners-Problems-or-Patterns-or-Sample-solutions\n\n```\nclass Solution {\n    public int minimumEffort(int[][] tasks) {\n        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> (b[1] - b[0]) - (a[1] - a[0]));\n        \n        long min = 0;\n        long max = 0;\n        \n        for (int[] t : tasks) {\n            maxHeap.add(t);\n            min += t[0]; // the result can not be smaller than min\n            max += t[1]; // the result can not be greater than max\n        }\n\t\t\n\t\t// BST  - Binary search tree\n        while (min < max) {\n            long mid = (max + min) / 2;\n            PriorityQueue<int[]> new_pq = new PriorityQueue(maxHeap);\n                \n            if (isValid(new_pq, mid)) {\n                max = mid;\n            } else {\n                min = mid + 1;\n            }\n        } \n        \n        return (int)min;\n    }\n    \n    public boolean isValid(PriorityQueue<int[]> maxHeap, long mid) {\n        while (!maxHeap.isEmpty()) {\n            int[] top = maxHeap.poll(); \n            \n            if (mid < top[1])\n                return false;\n            mid -= top[0];\n        }\n        return true;\n    }\n}\n```\n\n\n\n**Idea 2 : Greedy **\n \nSort by diff (task[1] - task[0])\n\nWhy sort that way ?\n - Because we need to save the most energy for the next one\n\n\nLook at 2 examples: \n1. example 1: [1-3] and [5-10]; which one you want to solve first? \n1. example 2: [1-6] and [9-10]; now which one? \n\n\n```\nclass Solution {\n    public int minimumEffort(int[][] tasks) {\n        Arrays.sort(tasks, (a, b) -> (b[1] - b[0]) - (a[1] - a[0]));\n        \n        int res = 0, energy = 0;\n        \n        for (int[] task : tasks) {\n            if (energy < task[1]) { // if we do not have enough energy for the next one\n                res += task[1] - energy;\n                energy = task[1];\n            }\n            \n            energy -= task[0];\n        }\n        return res;\n    }\n}\n```
[]