该站点上有N座建筑物,范围从0到N-1。每个员工在其中一栋建筑物中都有一个办公空间。现在,员工可以请求将其从当前的建筑物X移到另一座建筑物Y。
class Request {
String employeeName;
int fromBuilding;
int toBuilding;
}
最初,所有建筑物都已满。仅当Y楼中有人提出可实现的搬迁要求时,才可以实现X到Y的要求。给出请求的愿望清单有助于我们规划构建交换的最佳方法。满足最大请求数量的计划被认为是最好的。
Example 1:
Input:
["Alex",1,2]
["Ben",2,1]
["Chris",2]
["David",3]
["Ellen",3,1]
["Frank",4,5]
Output: [["Alex","Bem"],["Chris","David","Ellen"]]
Example 2:
Input:
["Adam",2]
["Brian",1]
["Carl",5]
["Dan",5,1]
["Eric",3]
["Fred",4]
Output: [["Adam","Eric","Fred","Carl","Dan"]]
https://leetcode.com/discuss/interview-question/325840/amazon-phone-screen-moving-requests
==
实际上,这个问题来自leetcode,我试图找出解决方法,但我没有。
我找到了解决此问题的好方法: (当前门牌号=>下一个门牌号)
(1 => 2),(2 => 6),(6 => 1),(2=>3),(3=>4),(4=>7),(7=>3),(4=>5),(5=>1),(1=>2)
我需要输出(1、2、6),(3、4、7)=> 6个请求而不是(1、2、3、4、5)=> 5个请求。 是DP还是贪婪?如何处理边缘的重量(重复请求)?
谢谢!