【贪心算法】POJ-3190 区间问题
一、题目
Description
Oh those picky N (1 <= N <= 50,000) cows! They are so picky that each one will only be milked over some precise time interval A..B (1 <= A <= B <= 1,000,000), which includes both times A and B. Obviously, FJ must create a reservation system to determine which stall each cow can be assigned for her milking time. Of course, no cow will share such a private moment with other cows.
Help FJ by determining:
The minimum number of stalls required in the barn so that each cow can have her private milking period
An assignment of cows to these stalls over time
Many answers are correct for each test dataset; a program will grade your answer.
Input
Line 1: A single integer, N
Lines 2..N+1: Line i+1 describes cow i's milking interval with two space-separated integers.
Output
Line 1: The minimum number of stalls the barn must have.
Lines 2..N+1: Line i+1 describes the stall to which cow i will be assigned for her milking period.
Sample Input
5
1 10
2 4
3 6
5 8
4 7
Sample Output
4
1
2
3
2
4
Hint
Explanation of the sample:
Here's a graphical schedule for this output:
Time 1 2 3 4 5 6 7 8 9 10
Stall 1 c1>>>>>>>>>>>>>>>>>>>>>>>>>>>
Stall 2 .. c2>>>>>> c4>>>>>>>>> .. ..
Stall 3 .. .. c3>>>>>>>>> .. .. .. ..
Stall 4 .. .. .. c5>>>>>>>>> .. .. ..
Other outputs using the same number of stalls are possible.
二、思路&心得
- 贪心策略:先将所有数据按照开始时间start从小到大进行排序,然后以结束时间end为关键字维护一个最小优先队列。
- 开始时先将排序后的第一个数据加入到优先队列中,然后依次扫描数据,若start大于队首元素的end值,则弹出队首元素,并将此时的数据加入到优先队列中,同时更新每个元素对应的stall[i]值。
- 算法结束时,队列的大小即为所需要的stall个数。
- 在定义结构体时,加入pos位置元素,以保存每个数据对应的原始位置,因为输出要求按照原始数据的顺序进行输出的。
三、代码
#include<cstdio>
#include<queue>
#include<algorithm>
#define MAX_SIZE 50005
using namespace std;
struct P {
int start;
int end;
int pos;
} a[MAX_SIZE];
int N;
int stall[MAX_SIZE];
bool cmp(P a, P b) {
return a.start < b.start;
}
bool operator > (P a, P b) {
return a.end > b.end;
}
void solve() {
priority_queue<P, vector<P>, greater<P> > que;
for (int i = 0; i < N; i ++) {
scanf("%d %d", &a[i].start, &a[i].end);
a[i].pos = i;
}
sort(a, a + N, cmp);
fill(stall, stall + N, 1);
que.push(a[0]);
for (int i = 1; i < N; i ++) {
P temp = que.top();
if (a[i].start > temp.end) {
stall[a[i].pos] = stall[temp.pos];
que.pop();
} else {
stall[a[i].pos] = que.size() + 1;
}
que.push(a[i]);
}
printf("%d\n", que.size());
for (int i = 0; i < N; i ++) {
printf("%d\n", stall[i]);
}
}
int main() {
scanf("%d", &N);
solve();
return 0;
}
最新文章
- python之浅拷贝和深拷贝
- CVTE实习求职经历
- 2016 ICPC大连站---F题 Detachment
- Understanding Convolutions
- Solved: Qt Library LNK 2001 staticMetaObject error
- Linix常用命令
- Yii源码阅读笔记(二)
- bzoj2242: [SDOI2011]计算器 &;&; BSGS 算法
- Unique Paths ——LeetCode
- HTML的表格玩法
- jQuery插件-jgcharts实现Javascript制作Google Charts
- jmeter java请求
- Java 之JavaBean 、EJB 和POJO
- java内部发送http请求并取得返回结果,修改response的cookie
- php正则相关知识点
- Maven原型骨架及常见问题
- OO第一单元总结与心得体会
- 野(wild)指针与悬空(dangling)指针
- 《大话设计模式》c++实现 状态模式
- Python3.5+PyQt5多线程+itchat实现微信防撤回桌面版代码
热门文章
- 【10.14】Bug Bounty Write-up总结
- flutter快速入门
- Android开发——布局性能优化的一些技巧(二)
- 2069: [POI2004]ZAW
- Kubernetes学习之路(十三)之Pod控制器--DaemonSet
- JAVA Eclipse 快捷键 ctrl+f 查找/替换 字符串
- Object Relational Mapping框架之Hibernate
- PKCS#7
- [Unity Shader] 坐标变换与法线变换及Unity5新增加的内置函数
- 人工智能AI芯片与Maker创意接轨 (上)