2023-09-11力扣每日一题

链接：

630. 课程表 III

题意

一个课程花费ai天，需要在bi天之前修好才算成功，求最多能修几个课

解：

ddl越靠后的应该越晚做，所以先按照b排序（这还用问为什么吗？

然后通过维护一个优先队列存储目前已经修的课程，按照a排序，花费时间越多的越不划算

这是我们可以发现，越后面进来的课，ddl越晚，那么当这个后面来的课a大于队列内的数字时，不能修

当这个后面来的课a小于队列内的数字时，是更优解，替换队列内的最大数（由于用时短，ddl晚，则一定合法

实际代码：

#include
using namespace std;
static bool cmp(vector& lhs,vector& rhs)
{
	if(lhs[1]==rhs[1]) return lhs[0]>& courses)
{
	sort(courses.begin(),courses.end(),cmp);
	priority_queuep_q;
	int sum=0;
	
	for(auto& course:courses)
	{
		int need=course[0],ddl=course[1];
		if(sum+need<=ddl)
		{
			sum+=need;
			p_q.push(need);
		}
		else if(!p_q.empty() && p_q.top()>need)
		{
			sum-=p_q.top()-need;
			p_q.pop();
			p_q.push(need);
		}
	}
	return p_q.size();
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

限制：

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