X

LEETCODE 630. Course Schedule III 解题思路分析

题目大意:

课程表 III

这里有 n 门不同的在线课程,他们按从 1 到 n 编号。每一门课程有一定的持续上课时间(课程时间)t 以及关闭时间第 d 天。一门课要持续学习 t 天直到第 d 天时要完成,你将会从第 1 天开始。

给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

示例:

输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出: 3
解释:
这里一共有 4 门课程, 但是你最多可以修 3 门:
首先, 修第一门课时, 它要耗费 100 天,你会在第 100 天完成, 在第 101 天准备下门课。
第二, 修第三门课时, 它会耗费 1000 天,所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。
第三, 修第二门课时, 它会耗时 200 天,所以你将会在第 1300 天时完成它。
第四门课现在不能修,因为你将会在第 3300 天完成它,这已经超出了关闭日期。

提示:

  1. 整数 1 <= d, t, n <= 10,000 。
  2. 你不能同时修两门课程。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=650

解题思路分析:

这道题需要使用到排序和优先队列PriorityQueue。另外解题的核心思路也会利用到贪心思想。

  1. 首先我们需要明确一点,先学习deadline靠前的可以省下更多的时间去学习其他课程。虽然这不一定是全局最优解,但我们有其他办法在后面进行修正。
  2. 根据第一点的结论,我们将课程数组按照deadline进行升序排序。
  3. 创建一个优先队列PriorityQueue,用来保存可以学习的课程,Queue中保存所有已选课程所消耗的时间,并且时间按照由多到少降序排列。另外建立一个变量day,代表当前日期。
  4. 循环课程列表从中取出每一门课,如果当前日期day加上该课消耗的时间小于等于这门课程的deadline,那么我们将这门课程所消耗的时间加入到Queue中。
  5. 如果当前日期day加上当前课程消耗的时间大于这门课的deadline,说明从当前日期开始到deadline之前无法完成该课程的学习。那么我们可以考虑从Queue中拿掉一门最消耗时间的课程(一定要大于当前课程的时间,否则没有意义),来换取更多的时间学习当前这门课。然后再将当前课程加入到Queue中。这样一来虽然一减一加,Queue中元素的个数没有发生改变,但是我们去掉了时间最长的课程,也就是将Queue中的总时间减少,对于全局结果来说会做出一定的优化。重复上述过程直到循环完每一节课。
  6. 最终Queue中元素的个数即是返回结果

实现代码:

public int scheduleCourse(int[][] courses) {
    Arrays.sort(courses,(a,b)->a[1]-b[1]); // 按照deadline进行升序排序
    // 保存所有可选课程
    PriorityQueue<Integer> q=new PriorityQueue<>((a,b)->b-a);
    int day=0; // 当前日期
    // 循环所有课程
    for(int[] c : courses){
        // 如果从当前开始学这门课,能赶上该课的deadline的话
        if(day+c[0]<=c[1]){
            q.offer(c[0]);  // 将该课程的时长加入Queue
            day+=c[0];  // 同时更新日期为这门课学完后的日期
        }else{ // 如果从当前开始学这门课,不能赶上该课的deadline的话
            // 如果已选课程中时长最大的课程大于当前课程的时长
            if(q.size()>0&&c[0]<q.peek()){
                // 放弃学习时长最长的那门课
                int remove=q.poll();
                // 日期减去那门课要花费的时间
                day-=remove;
                // 将当前课程加入Queue
                q.offer(c[0]);
                // 同时更新日期为当前这门课学完后的日期
                day+=c[0];
            }
        }
    }
    return q.size();
}

本题解法执行时间为30ms。

Runtime: 30 ms, faster than 83.72% of Java online submissions for Course Schedule III.

Memory Usage: 48.4 MB, less than 100.00% of Java online submissions for Course Schedule III.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-630-course-schedule-iii-解题思路分析/
Categories: leetcode
kwantong: