时间戳

首页 > 解决方案 > 面试问题：如何满足最大数量的搬家要求

algorithm - 面试问题：如何满足最大数量的搬家要求

问题描述

场地上有 N 个建筑物，范围从 0 到 N-1。每位员工在其中一栋建筑中都有一个办公空间。新员工可能会要求从当前的 X 楼搬到另一栋 Y 楼。搬迁请求由

class Request {
    String employeeName;
    int fromBuilding;
    int toBuilding;
}

最初所有建筑物都已满。从 X 楼到 Y 楼的请求只有在 Y 楼有人提出可实现的搬迁请求并因此产生空缺时才能实现。鉴于请求的愿望清单，可帮助我们计划构建交换的最佳方式。满足最大请求数的计划被认为是最好的。

Example 1:

Input:
["Alex", 1, 2]
["Ben", 2, 1]
["Chris", 1, 2]
["David", 2, 3]
["Ellen", 3, 1]
["Frank", 4, 5] 

Output: [["Alex", "Bem"], ["Chris", "David", "Ellen"]]

Example 2:

Input:
["Adam", 1, 2]
["Brian", 2, 1]
["Carl", 4, 5]
["Dan", 5, 1]
["Eric", 2, 3]
["Fred", 3, 4]

Output: [["Adam", "Eric", "Fred", "Carl", "Dan"]]

这个问题取自这里的 leet 代码：

https://leetcode.com/discuss/interview-question/325840/amazon-phone-screen-moving-requests

我正在尝试在 python 中执行此操作，我认为创建一个表示图形的字典将是一个好的开始，但不确定下一步该做什么。

```
def findMovers(buildReqs):
    graph={}
    for i in buildReqs:
        if i[1] not in graph:
            graph[i[1]]=[i[2]]
        else:
            graph[i[1]].append(i[2])
```

标签： algorithmgraph

解决方案

制作一个二分图，一侧是当前办公室，另一侧是未来办公室。

为留在当前办公室的人绘制得分为 0 的边，为搬到任何想要的新办公室的人绘制得分为 1 的边。

找到最大权重二分匹配：https ://en.wikipedia.org/wiki/Assignment_problem

推荐阅读