630. 课程表 III (opens new window)

1.贪心+优先队列

解题思路：在截止时间的限制下，维护一个总耗时最短的课程序列。

• 对所有课程按截止时间进行排序
• 创建一个降序的优先级队列
• 每次遍历时算法如下：
  • 当前课程时间加入“当前时间”的总和
  • 如果“当前时间”已经超过当前课程的截止时间，则从队列中删除持续时间最长的课程。

从队列中删除最长时间的课程，可以保证当前已修课程总耗时最短，但如何证明删除后已满足的最大课程数量依然保持不变？具体来说，假设当前课程(cost，limit)，那么如何证明 curr+cost-max(queue) <limit？证明如下:

显然，在遍历过程中 curr < limit；假设 k=max(curr,cost)，那么一定有 curr + cost - k <= curr <limit。相当于删除耗时最大的课程。

✨多维贪心技巧：优先对时刻、数量等限制条件排序。另一维可以通过数据存取方式体现贪心策略。

class Solution {
    public int scheduleCourse(int[][] courses) {
       Arrays.sort(courses,new Comparator<int[]>(){
            public int compare(int[] a,int[] b){
                if(a[1]!=b[1]) return a[1]-b[1];
                else return a[0]-b[0];
            }
        });
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return b-a;
            }
        });
        int step=0;
        int res=0,curr=0;
        for(int i=0;i<courses.length;i++){
            queue.offer(courses[i][0]);
            curr+=courses[i][0];
            step++;
            if(curr>courses[i][1]){
                    curr-=queue.poll();
                    step--;
            }
            res=Math.max(res,step);
        }
        return res;
    }
}