刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

商场导购

【题目描述】

作为 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。

使用微信搜索喵呜刷题,轻松应对考试!

答案:

3

解析:

【喵呜刷题小喵解析】:观察输入样例2,首先观察每个时间段,然后找到重叠的时间段。比如时间段[24,29]和[26,32]有重叠,所以可以让同一个导购负责。同样,[11,14]和[18,21]也有重叠,也可以让同一个导购负责。最后,[39,39]和[39,44]虽然结束时间相同,但开始时间不同,所以不能让同一个导购负责。因此,最少需要3位导购。对于一般的情况,我们需要遍历每个时间段,找到重叠的时间段,然后统计需要的最少导购数。可以使用贪心算法来解决这个问题。
创作类型:
原创

本文链接:商场导购 【题目描述】 作为 H 国知名商人,东东在 D 城的市中心开了一家高人气商场,商场提供极其

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share