任务调度优化 - 解题思路

这段代码使用贪心算法和优先队列来解决任务调度问题，目标是最大化能按时完成的任务数量。

算法思路

1. 输入处理：

   • 读取任务数量n
   • 读取每个任务的两个属性：所需工作时间(first)和截止时间(second)

2. 任务排序：

   • 按照任务的截止时间从早到晚进行排序

3. 贪心调度：

   • 使用最大堆（优先队列）来管理当前已选任务的工作时间
   • 遍历排序后的任务列表：
     • 将当前任务加入队列
     • 累加总工作时间
     • 如果总工作时间超过当前任务的截止时间：
       • 从队列中移除工作时间最长的任务
       • 减少总工作时间
       • 减少完成任务计数

4. 结果输出：

   • 输出能按时完成的最大任务数量

关键点

• 贪心策略：优先处理截止时间早的任务
• 使用最大堆快速获取工作时间最长的任务
• 当时间冲突时，舍弃最耗时的任务以保留更多任务完成的可能
• 时间复杂度：O(n log n)（排序和优先队列操作）
• 空间复杂度：O(n)（存储任务和优先队列）

该算法能高效地找到可以按时完成的最大任务子集，适用于任务调度优化场景。

#include<iostream>
#include<algorithm>
#include<string>
#include<map>//int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};
#include<set>//int gcd(int a,int b){return b?gcd(b,a%b):a;}
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<stdlib.h>
#include<cstdio>
#define mod 1e9+7
#define ll long long
using namespace std;
int n;
pair<int,int> x[800001]; 
int cmp(pair<int,int>a,pair<int,int>b){
	return a.second<b.second;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d %d",&x[i].first,&x[i].second);//需要的工作时间和截止日期 
	}
	sort(x,x+n,cmp);   //按截止日期排序 
	int s=n,sum=0;
	priority_queue<int> q;  //默认是从大到小排序(需要的工作时间)
	for(int i=0;i<n;++i){
		q.push(x[i].first);
		sum+=x[i].first;
		if(sum>x[i].second){
			s--;
			sum-=q.top();  //舍去需要的工作时间最久的 
			q.pop(); 
		}
	}
	printf("%d",s);
    return 0;
}