首页 > 代码库 > hihoCoder 1309:任务分配 贪心 优先队列
hihoCoder 1309:任务分配 贪心 优先队列
#1309 : 任务分配
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
给定 N 项任务的起至时间( S1, E1 ), ( S2, E2 ), ..., ( SN, EN )， 计算最少需要多少台机器才能按时完成所有任务。
同一时间一台机器上最多进行一项任务，并且一项任务必须从头到尾保持在一台机器上进行。任务切换不需要时间。
输入
第一行一个整数 N，(1 ≤ N ≤ 100000)，表示任务的数目。 以下 N 行每行两个整数 Si, Ei，(0 ≤ Si < Ei ≤ 1000000000)，表示任务的起至时间。
输出
输出一个整数，表示最少的机器数目。
- 样例输入
51 102 76 93 47 10
- 样例输出
3
题目连接：http://hihocoder.com/problemset/problem/1309
题意：n个时间，每个时间有开始时间和结束时间，问至少需要几台机器才能全部完成。
思路：贪心。时间按s，e升序排序。利用优先队列。
代码：
贪心 优先队列#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;const int MAXN=1e6+100;struct cmp{ bool operator ()(int &a,int &b) { return a>b; }};priority_queue<int,vector<int>,cmp>Q;struct node{ int s,e;} x[MAXN];int cmp(node a,node b){ if(a.s!=b.s) return a.s<b.s; else return a.e<b.e;}int sign[MAXN];int main(){ int i,j,n; while(~scanf("%d",&n)) { for(i=1; i<=n; i++) scanf("%d%d",&x[i].s,&x[i].e); sort(x+1,x+n+1,cmp); Q.push(0); for(i=1; i<=n; i++) { if(Q.top()<=x[i].s) { Q.pop(); Q.push(x[i].e); } else Q.push(x[i].e); } cout<<Q.size()<<endl; } return 0;}
hihoCoder 1309:任务分配 贪心 优先队列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。