0630. Course Schedule III - kumaeki/LeetCode GitHub Wiki

630. Course Schedule III

There are n different online courses numbered from 1 to n.

You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

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

Return the maximum number of courses that you can take.

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation: 
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day. 
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day. 
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

Constraints:

  • 1 <= courses.length <= 104
  • 1 <= durationi, lastDayi <= 104

解法1

这是看的标准答案.
每次从已完成course中替换掉最长时长的course时, 虽然不知道具体替换掉的是第几个(虽然可以用更复杂的数据结构来保存信息, 但是没有必要), 但是因为在进行处理之前已经根据事时限进行了排序(升序), 就可以保证只要替换掉之前的长course, 那么后面的短course肯定可以完成.

public class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照完成时间期限顺序排列
        Arrays.sort(courses, (x1, x2) -> x1[1] - x2[1]);
        // 当前时间
        int time = 0;
        // 完成course数
        int count = 0;
        for (int i = 0; i < courses.length; i++) {
            int[] course = courses[i];
            // 如果当前课程可以完成
            if (time + course[0] <= course[1]) {
                time += course[0];
                count++;
            } 
            // 如果当前课程无法完成
            else {
                
                // 找出之前完成课程中最大长度的课程
                int max_i = i;
                for (int j = 0; j < i; j++) {
                    if (courses[j][0] > courses[max_i][0])
                        max_i = j;
                }
                // 将该课程的时间与当前课程交换
                if (courses[max_i][0] > courses[i][0]) {
                    time += courses[i][0] - courses[max_i][0];
                }
                // 将无法完成的课程的时常改为-1
                courses[max_i][0] = -1;
            }
        }
        return count;
    }
}

解法2

解法1改动了原始的数组, 不优雅.
更好的方法是用PriorityQueue来存储可以完成的课程长度, 碰到无法完成的课程时, 从中去掉一个最长课程即可.

public class Solution {
    public int scheduleCourse(int[][] courses) {
        // 按照完成时间期限顺序排列
        Arrays.sort(courses, (x, y) -> x[1] - y[1]);
        // que按照倒序取出元素(poll时取出最大值)
        PriorityQueue<Integer> que = new PriorityQueue<Integer>((x, y) -> y - x);
        // 当前时间
        int time = 0;
        
        for(int[] course : courses){
            // 计算当前时间
            time += course[0];
            // 当前course加入que
            que.add(course[0]);
            
            // 如果当前course无法完成
            // 出去que中所需时常最长的course
            if(time > course[1])
                time -= que.poll();
        }
        
        return que.size();
    }
}
⚠️ **GitHub.com Fallback** ⚠️