# 630. Course Schedule III

给定一系列课程，每个课程有持续时长和课程报名截止时间，问最多能上多少门课。时间点问题先根据截止时间排序，这个问题可以看成给定时间内能最多选多少门课，也就是一个背包问题: 课程持续时间对应物品占重，截止时间对应背包容积。

```cpp
/*
 * @lc app=leetcode id=630 lang=cpp
 *
 * [630] Course Schedule III
 *
 * https://leetcode.com/problems/course-schedule-iii/description/
 *
 * algorithms
 * Hard (32.35%)
 * Likes:    476
 * Dislikes: 24
 * Total Accepted:    14.2K
 * Total Submissions: 43.5K
 * Testcase Example:  '[[100,200],[200,1300],[1000,1250],[2000,3200]]'
 *
 * There are n different online courses numbered from 1 to n. Each course has
 * some duration(course length) t and closed on dth day. A course should be
 * taken continuously for t days and must be finished before or on the dth day.
 * You will start at the 1st day.
 * 
 * Given n online courses represented by pairs (t,d), your task is to find the
 * maximal number of courses that can be taken.
 * 
 * Example:
 * 
 * 
 * Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
 * Output: 3
 * Explanation: 
 * There're 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.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * The integer 1 <= d, t, n <= 10,000.
 * You can't take two courses simultaneously.
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const auto &a, const auto &b){
            return a[1] < b[1];
        });
        const int M = courses.size(), N = courses[M - 1][1];
        vector<vector<int>> dp(M + 1, vector<int>(N + 1));
        for (int i = 1; i <= M; ++i) {
            for (int j = 1; j <= N; ++j) {
                // 不选
                dp[i][j] = dp[i - 1][j];
                // 选
                if (j >= courses[i - 1][0] && j <= courses[i - 1][1]) {
                    dp[i][j] = max(dp[i][j], dp[i - 1][j - courses[i - 1][0]] + 1);
                } else {
                    // j超出ddl: courses[i - 1][1]
                    dp[i][j] = max(dp[i][j], dp[i][j - 1]);
                }
            }
        }
        return dp[M][N];
    }
};
// @lc code=end

```

不过这个解法需要遍历所有的时间，当截止时间设的很大的时候会TLE。实际上这个背包是满足贪心条件的特殊背包，给定容积问最多能放多少物件，那选容积最小的能放多少就是多少了。因此排好序后用维持一个max heap，每次把时长最大的pop出来把当前放进去，和选前K小一个套路。

```cpp
/*
 * @lc app=leetcode id=630 lang=cpp
 *
 * [630] Course Schedule III
 *
 * https://leetcode.com/problems/course-schedule-iii/description/
 *
 * algorithms
 * Hard (32.35%)
 * Likes:    476
 * Dislikes: 24
 * Total Accepted:    14.2K
 * Total Submissions: 43.5K
 * Testcase Example:  '[[100,200],[200,1300],[1000,1250],[2000,3200]]'
 *
 * There are n different online courses numbered from 1 to n. Each course has
 * some duration(course length) t and closed on dth day. A course should be
 * taken continuously for t days and must be finished before or on the dth day.
 * You will start at the 1st day.
 * 
 * Given n online courses represented by pairs (t,d), your task is to find the
 * maximal number of courses that can be taken.
 * 
 * Example:
 * 
 * 
 * Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
 * Output: 3
 * Explanation: 
 * There're 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.
 * 
 * 
 * 
 * 
 * Note:
 * 
 * 
 * The integer 1 <= d, t, n <= 10,000.
 * You can't take two courses simultaneously.
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const auto &a, const auto &b){
            return a[1] < b[1];
        });
        priority_queue<int> q;
        // 总上课耗时
        int t = 0;
        for (const auto &c : courses) {
            // 选了后不超过截止
            if (t + c[0] <= c[1]) {
                t += c[0];
                q.push(c[0]);
            } else if (!q.empty() && q.top() > c[0]) {
                t += c[0] - q.top();
                q.pop();
                q.push(c[0]);
            }
        }
        return q.size();
    }
};
// @lc code=end
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/bei-bao-wen-ti/630.-course-schedule-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.