630. Course Schedule III

Question

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [duration<sub>i</sub>, lastDay<sub>i</sub>] indicate that the i<sup>th</sup> course should be taken continuously for duration<sub>i</sub> days and must be finished before or on lastDay<sub>i</sub>.

You will start on the 1<sup>st</sup> day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Solution

贪心算法，优先级队列实现。
优先选择截止日期更短的课程。
优先级队列pq记录当前已选课程，按持续时间从长到短排列。
同时维护当前的日期curDay。

当当前选择的课程截止日期晚于curDay加上当前的持续时间duration时，查看大根堆里最长的课程longestDuration。如果最长的时间大于当前时间，则将其挤出，并将当前课程加入。

如果当前课程截止日期晚于curDay，则直接将其加入队列中，并更新curDay。

Code

class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        int curDay = 0;
        for(int[] course : courses){
            int duration = course[0];
            int lastDay = course[1];
            
            if(curDay + duration > lastDay){    //大于截止日期
                if(pq.isEmpty()) continue;
                int longestDuration = pq.peek()[0];
                if(longestDuration > duration){ //替换到当前队列中持续日期最长的课程
                    curDay -= pq.poll()[0];
                    curDay += duration;
                    pq.offer(course);
                }
            }
            else{   //小于截止日期则加入选课
                curDay += duration;
                pq.offer(course);
            }
        }
        return pq.size();
    }
}