Greedy Algorithm with FULL and EASY Explanation with NO fancy ideas or concepts!!!!!
The most critical part of greedy algorithm is why we sort the array by its minimum - cost (that is tasks[i][1] - tasks[i][0]) value? If people understand this t
The most critical part of greedy algorithm is why we sort the array by its `minimum - cost (that is tasks[i][1] - tasks[i][0])` value? If people understand this trick, the leftover is nothing but iteration. \n\nFirstly, please read the question **course scheduler III**: https://leetcode.com/problems/course-schedule-iii/ (**Read question only. Don\'t read the approach first**)\n\n**Do you notice the similarity between these two questions?** \nThe minimum energy requirement for each task is equivalent to the following condition: \n* The energy after taking this task is no less than minimum - cost\n\nIf we treat the energy as time (our time goes from higher to lower, but it doesn\'t matter), this condition is basically saying \n* this task (course) should be taken no later than time = minimum - cost.\n\nOk, now we find that these two questions **are almost the same.**\n\nSecondly, please understand the following part in approach 2 explanation for course scheduler III.\n\n* From the above example, we can conclude that it is always profitable to take the course with a smaller end day prior to a course with a larger end day. This is because, the course with a smaller duration, if can be taken, can surely be taken only if it is taken prior to a course with a larger end day.\n\nThis sentance is basically saying we could sort our array by `minimum - cost (that is tasks[i][1] - tasks[i][0])` and take tasks one by one with the order. Then, here comes our greedy solution: \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        int ans = 0, cur = 0, len = tasks.length;\n        for(int i = 0; i < len; i++) {\n            if(cur < tasks[i][1]) {\n                ans += tasks[i][1] - cur;\n                cur = tasks[i][1] - tasks[i][0];\n            }\n            else {\n                cur -= tasks[i][0];\n            }\n        }\n        return ans;\n    }\n}\n```\nBonus part: **course scheduler III** is a really good question that you must remember because it is not a normal matroid structure (why it is not matroid? Please refer to \u201CIntroduction to Algorithms\u201C Third edition, Introduction part of 16.4 Matroids and greedy methods. This kind problem is activity selection problem).
[]