LeetCode刷题记158-1665. 完成所有任务的最少初始能量

LeetCode刷题记158

1665. 完成所有任务的最少初始能量

class Solution {
          
   
    public int minimumEffort(int[][] tasks) {
          
   
        // 直接数组排序快一点
        Arrays.sort(tasks, new Comparator<int[]>() {
          
   
            @Override
            public int compare(int[] o1, int[] o2) {
          
   
                if (o1[1] - o1[0] == o2[1] - o2[0]) {
          
   
                    return o2[1] - o1[1]; // 相等的话，需要大的在其前面
                } else {
          
    // 需要和最低差值大的在前面
                    return o2[1] - o2[0] - (o1[1] - o1[0]);
                }
            }
        });
        int ans = 0;
        int rest = 0;
        for (int i = 0; i < tasks.length; i ++) {
          
   
            if (tasks[i][1] > rest) {
          
    // 需要的大于上一个任务剩余的
                ans += tasks[i][1] - rest; // 那就补充一下初始能量
                rest = tasks[i][1] - tasks[i][0]; // 最小剩余就是完成这次任务之后的
            } else {
          
    // 上次任务剩下的能量够用了
                rest -= tasks[i][0]; //减去这次用的
            }
        }
        // 上面直接排序比下面用优先队列快
        // PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<Pair<Integer, Integer>>(
        //     new Comparator<Pair<Integer, Integer>>() {
          
   
        //         @Override
        //         public int compare(Pair<Integer, Integer> a, Pair<Integer, Integer> b) {
          
   
        //             if (a.getKey() == b.getKey()) {
          
   
        //                 return b.getValue() - a.getValue();
        //             } else {
          
   
        //                 return b.getKey() - a.getKey();
        //             }
        //         }
        //     }
        // );
        // for (int i = 0; i < tasks.length; i ++) {
          
   
        //     queue.add(new Pair(tasks[i][1] - tasks[i][0], tasks[i][1]));
        // }
        // int ans = 0;
        // int rest = 0;
        // while (!queue.isEmpty()) {
          
   
        //     Pair<Integer, Integer> e = queue.poll();
        //     // System.out.println(e);
        //     if (e.getValue() > rest) {
          
   
        //         ans += e.getValue() - rest; 
        //         rest = e.getKey();
        //     } else {
          
   
        //         rest -= e.getValue() - e.getKey();
        //     }
        // }
        return ans;
    }
}