LeetCode - 630 课程表Ⅲ

青旅半醒 2023-09-23 23:54 15阅读 0赞

**目录**

题目来源

题目描述

示例

提示

题目解析

算法源码

--------------------

### 题目来源 ###

[630. 课程表 III - 力扣（LeetCode）][630. _ III - _LeetCode]

### 题目描述 ###

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses\[i\] = \[durationi, lastDayi\] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

### 示例 ###

<table style="width:619px;"> 
 <tbody> 
  <tr> 
   <td style="width:76px;">输入</td> 
   <td style="width:540px;">courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]</td> 
  </tr> 
  <tr> 
   <td style="width:76px;">输出</td> 
   <td style="width:540px;">3</td> 
  </tr> 
  <tr> 
   <td style="width:76px;">说明</td> 
   <td style="width:540px;">这里一共有 4 门课程，但是你最多可以修 3 门：<br> 首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。<br> 第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。<br> 第三，修第 2 门课，耗时 200 天，在第 1300 天完成。<br> 第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:622px;"> 
 <tbody> 
  <tr> 
   <td style="width:78px;">输入</td> 
   <td style="width:543px;">courses = [[1,2]]</td> 
  </tr> 
  <tr> 
   <td style="width:78px;">输出</td> 
   <td style="width:543px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:78px;">说明</td> 
   <td style="width:543px;">无</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:622px;"> 
 <tbody> 
  <tr> 
   <td style="width:78px;">输入</td> 
   <td style="width:543px;">courses = [[3,2],[4,3]]</td> 
  </tr> 
  <tr> 
   <td style="width:78px;">输出</td> 
   <td style="width:543px;">0</td> 
  </tr> 
  <tr> 
   <td style="width:78px;">说明</td> 
   <td style="width:543px;">无</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

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

### 题目解析 ###

本题虽然是一道hard题目，但是有固定的解题套路，因此一旦掌握解题套路，本题就很easy了。

本题的解题套路如下：

首先，将courses数组元素按照结束时间lastDayi进行升序排序。

然后，定义一个优先队列，course的durationi越大，优先级越高。

之后，定义一个curDay来记录当前时间，初始为0，

接下来，遍历courses数组，这样遍历出来的每一个course都是最接近curDay的，设courses\[i\] = \[durationi, lastDayi\]，如果：

*  curDay + durationi <= lastDayi，则说明当前时间如果选择上courses\[i\]，则可以在其结束时间前学完。此时我们可以将courses\[i\]加入优先队列中，并更新curDay = curDay + duration。
 *  curDay + durationi > lastDayi，则说明当前时间如果选择上courses\[i\]，则无法在其结束时间前学完，此时我们应该做如下判断：

> 题目要求我们上最多的课，因此我们应该尽量上duration短的课程。
> 
> 此时，我们应该获取优先队列堆顶元素，因为优先队列是按照duration设置优先级的，duration越大优先级越高，越靠近堆顶。
> 
> 如果当前课程的durationi < 优先队列最大的top\_duration，则有必要将优先队列堆顶的课程弹出，即不学习这门课程了，这样就节省出了top\_duration的时间，并且curDay也会跟着降低，即curDay = curDay - top\_duration。
> 
> 此时，curDay + durationi <= lastDayi 必然成立，因此我们可以学习courses\[i\]课程，此时我们应该将courses\[i\]加入优先队列，并更新curDay = curDay + durationi。

### 算法源码 ###

class Solution {
        public int scheduleCourse(int[][] courses) {
            Arrays.sort(courses, (a, b) -> a[1] - b[1]);
            PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a);
    
            int curDay = 0;
            for(int[] course : courses) {
                int duration = course[0];
                int lastDay = course[1];
    
                if(curDay + duration <= lastDay) {
                    pq.offer(duration);
                    curDay += duration;
                } else {
                    if(pq.size() == 0) {
                        continue;
                    }
    
                    int maxDuration = pq.peek();
                    if(duration < maxDuration) {
                        pq.poll();
                        pq.offer(duration);
                        curDay += duration - maxDuration;
                    }
                }
            }
    
            return pq.size();
        }
    }

![1fd706436481493499bc97649dde0c6a.png][]

[630. _ III - _LeetCode]: https://leetcode.cn/problems/course-schedule-iii/submissions/
[1fd706436481493499bc97649dde0c6a.png]: https://img-blog.csdnimg.cn/1fd706436481493499bc97649dde0c6a.png