630. Course Schedule III

https://leetcode.com/problems/course-schedule-iii/

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

/*
 * @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小一个套路。

/*
 * @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