A39217. 商场导购【
填空题
困难
知识点
题目描述
商场导购
【题目描述】
作为 H 国知名商人，东东在 D 城的市中心开了一家高人气商场，商场提供极其贴心的五星级导购服务。 需要导购服务的顾客可以提前一天预约使用的时间段。目前有 N 位顾客预约了第二天导购服务，其中第 i 位顾客预约的时间段为 Ai 到 Bi，注意导购服务包括了 Ai 和 Bi两个时间段。很明显一位导购在同一个时间段只能服务一位客户。 为了节约人工成本，东东希望使用最少的导购满足全部顾客的要求。请你帮他求出第二天最少需要多少位导购。
【输入格式】
输入有两行，第一行为两个正整数 N，表示预约导购服务的顾客数量。 第 2 到 N+1 行，
每行两个整数 Ai，Bi，表示第 i 位顾客预约的时间段。
【输出格式】
输出一个整数，表示最少需要多少导购，可以满足全部顾客。
【输入样例 1】
5
1 10
2 5
5 8
3 6
6 10
【输出样例 1】
4
【样例 1 说明】
由于导购服务包括边界的时间段，所以[2, 5]和[5, 8]必须让不同的导购负责，那么只有[2, 5]和[6, 10]可以请同一个导购，其他都需要单独请导购。
【输入样例 2】
10
24 29
11 14
5 10
26 32
4 6
27 31
39 39
39 44
18 21
18 18
【输出样例 2】
3
【数据范围】
对于 30%的数据：1<= N<= 10；
对于 60%的数据：1<= N<= 100，1<= Ai<= Bi<= 100；
对于 100%的数据：1<= N<= 10000，1<= Ai<= Bi<= 5000。
参考答案
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 100005;
struct cows {
int l, r;
}
c[N];
bool cmp(cows a, cows b) {
return a.l < b.l;
}
int n, t[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d%d", &c[i].l, &c[i].r);
sort(c+1, c+n+1, cmp);
int cnt = 0, j = 1;
for (int i = 1; i <= n; i++) {
bool bl = 0;
for (; j < c[i].l; j++) //查找有时间的导购
if(t[j] > 0) {
t[j]--;
bl = 1;
break;
}
if(bl == 0) cnt++;
//如果没有找到，增加一个新导购
t[c[i].r]++;
}
printf("%d\n", cnt);
return 0;
}
上一题
下一题