遇到一个快递员取快递面试题，想请问波波老师解题思路

Question

一次面试中遇到这样一道题：“有若干个快递员，需要去不同地点取若干个快递，假设他们都处在同一水平线上，快递员和快递的位置分别记做x轴上不同的位置点，通过数组表示他们的位置。每个快递员在一个时间单位只能左移或者右移一个单位，或者原地不同，求最少需要多少个时间单位才能取完所有的快递，给的一个测试用例是，快递员的数组是persons=[2,8,7], 快递的数组是goods=[1,3,7,11], 最少需要3个时间单位才能取完所有快递：第一个快递员的线路是2->1->2->3, 用3个时间单位取到了位置为1和3的快递，第二个快递员的线路是8->9->10->11,用3个时间单位取到了位置为11的快递，第三个快递员的线路是7->7，用0个时间单位取到了位置为7的快递，因此答案是3个时间单位。快递数大于等于快递员数，他们的取值范围都在1到10的5次方之间”，我是觉得这道题应该是个贪心算法的问题，每一次循环都确定这一轮每个快递员应该去取哪个快递。但是写不出来，想请bobo老师帮忙分析下

Answer 1

liuyubobobo 2021-06-10 02:30:30

应该是二分搜索。搜索最小时间 t。

对于一个固定的 t，验证这些快递员是否可以取完这些快递，可以用贪心。对快递员和快递进行排序。最小的快递肯定由最小的快递员取，如果还有富裕时间，这个快递员可以去取次小的快递，以此类推。

继续加油！：）

• 提问者 铁甲小宝 #1

  谢谢波波老师，还有个问题，以这个测试用例为了，我排序后快递员位置persons=[2,7,8],goods=[1,3,7,11]，那么比如第一个快递(位置：1)应该由第一个快递员（位置：2）取，但是他取的时候其他快递员不是也可能要移动吗，而且第一个快递员取到了位置1的快递后，他的位置就到了1了，是不是需要重新计算？

• liuyubobobo 回复 提问者 铁甲小宝 #2

  没有特别理解你的问题。“他取的时候其他快递员不是也可能要移动”是的。但是我们相乘每个快递员依次移动不影响解的构成。我没有明白你说“他取的时候其他快递员不是也可能要移动吗”是针对什么反例？你觉得会有问题？重新计算具体是指什么？

• 提问者 铁甲小宝 回复 liuyubobobo #3

  以这个测试用例为例，快递员初始的位置是[2，7，8],快递初始位置是[1,3,7,11]，那么第一个快递，也就是位置为1的快递，肯定是应该由处在位置2的快递员去取，位置2的快递员花费一个时间单位，左移一个单位就可以取到快递1，我想知道的是，怎么判断他移动的这个时间单位其他快递员应该怎么做？比如以这道题为例，位置7的快递员应该原地不动就拿到了位置7的快递，位置8的快递员应该右移一个单位来靠近位置11的快递。我没想清楚一开始计算一下各个位置的快递距离快递员的距离，可以判断出来每个快递应该由哪个快递员取，但是在快递员取件的过程中他和别的快递的距离也就变了，比如位置2的快递员距离位置3的快递的初始距离是1，但是他取了位置为1的快递后和位置3的快递距离就变成2了。

点开查看后面2条评论