LeetCode 课程表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 <= d, t, n <= 10,000 。
你不能同时修两门课程。

思路分析： 这道题肯定是妥妥的贪心策略题，但是这道题右增加了难度。
首先我们按照（主）结束时间升序，（辅）上课时间进行排序，然后从第一门开始尽量学更多的课程。

class Solution {
public:
	//按照（主）结束时间升序，（辅）上课时间进行排序
	static bool myCmp(vector<int> &courseOne, vector<int> &courseTwo) {
		if (courseOne[1] == courseTwo[1]) {
			return courseOne[0] < courseTwo[0];
		}
		else {
			return courseOne[1] < courseTwo[1];
		}
	}
	int scheduleCourse(vector<vector<int>>& courses) {
		int canCourseCnt = 0, nowDay = 0;//可以学的课程数canCourseCnt ，现在的时间nowDay
		sort(courses.begin(), courses.end(), myCmp);//按照（主）结束时间升序，（辅）上课时间进行排序
		for (auto &course : courses) {
			if (nowDay + course[0] <= course[1]) {//如果这门课能学就尽量学
				canCourseCnt += 1;
				nowDay += course[0];//更新现在的时间
			}
		}
		return canCourseCnt;
	}
};

按照上面的逻辑，排序后为[[5, 5],[2, 6],[4, 6]]我们先学[5,5]到达了第5天，接下来学[2,6]学完这门课已经第7天了，超过了它的结束时间7。蛋式我们可以这样思考，我们可以使用[2,6]这门课区替代[5,5]这门课，因为[5,5]花的时间多，而[2,6]花的时间少。接着我们就能学习[4,6]了，因而答案是2。
辣么问题来了，我们什么时候可以进行替换呢？由于在学习课程之前，我们已经按照了结束时间进行升序排序，那么如果在课程k前有一门课程时间j超过了k的学习时间，则我们这时就能进行替换，因为j的学习时间大，并且k的结束时间晚，可以学习j就一定能学习k。

class Solution {
public:
	//按照（主）结束时间升序，（辅）上课时间进行排序
	static bool myCmp(vector<int> &courseOne, vector<int> &courseTwo) {
		if (courseOne[1] == courseTwo[1]) {
			return courseOne[0] < courseTwo[0];
		}
		else {
			return courseOne[1] < courseTwo[1];
		}
	}
	int scheduleCourse(vector<vector<int>>& courses) {
		int nowDay = 0;
        priority_queue<int> myPriorityQue;//优先队列，降序排列已经学过的课程花费的时间
		sort(courses.begin(), courses.end(), myCmp);//按照（主）结束时间升序，（辅）上课时间进行排序
		for (auto &course : courses) {
			if (nowDay + course[0] <= course[1]) {//这门课可以直接学习（贪心策略）
				nowDay += course[0];
                myPriorityQue.push(course[0]);
			}
            else if (!myPriorityQue.empty() && myPriorityQue.top() > course[0]){//如果这门课的学习时间小于之前学过的最长时间的课，则进行替换，因为这样可以空出更多的时间用来学习后面的课程
                nowDay = nowDay - myPriorityQue.top() + course[0];//回退这门最长的时间的课程，学习当前课程
                myPriorityQue.pop();
                myPriorityQue.push(course[0]);
            }
		}
		return myPriorityQue.size();
	}
};