What is the maximum number of achievable transfer requests in the "Maximum Number of Achievable Transfer Requests" problem?

The problem asks for the maximum number of transfer requests that can be fulfilled while ensuring that each building has a net zero transfer, meaning the number of employees leaving is equal to the number arriving.

How does backtracking help solve the problem?

Backtracking is used to explore all possible combinations of transfer requests. By pruning branches that lead to invalid solutions (like imbalanced transfers), we efficiently narrow down the search space.

What is pruning in the context of this problem?

Pruning involves eliminating infeasible solutions during the backtracking process, such as when the net transfer for any building becomes unbalanced. This saves computation time by avoiding unnecessary exploration of invalid paths.

How can bit manipulation be used in solving this problem?

Bit manipulation allows for efficient tracking of the state of employee transfers across buildings. Each building's net transfer can be represented as a bitmask, which helps quickly check if a solution is valid.

What is the time complexity of the "Maximum Number of Achievable Transfer Requests" problem?

The time complexity is O(2^(M * (M + N))), where M is the number of transfer requests and N is the number of buildings. This arises due to the backtracking approach with pruning, which explores all possible transfer combinations.

#1601

Hard

auto_awesome回溯·pruning

LeetCode 题解工作台

最多可达成的换楼请求数目

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。给你一个数组 requests ，其中 requests[i] = [from i , to i ] ，表示一个员工请求从编号为 from i 的楼搬到编号为 to i 的楼。一开始…

数组回溯位运算枚举

题目描述

我们有 n 栋楼，编号从 0 到 n - 1 。每栋楼有若干员工。由于现在是换楼的季节，部分员工想要换一栋楼居住。

给你一个数组 requests ，其中 requests[i] = [from_i, to_i] ，表示一个员工请求从编号为 from_i 的楼搬到编号为 to_i的楼。

一开始 所有楼都是满的，所以从请求列表中选出的若干个请求是可行的需要满足 每栋楼员工净变化为 0 。意思是每栋楼离开的员工数目等于该楼搬入的员工数数目。比方说 n = 3 且两个员工要离开楼 0 ，一个员工要离开楼 1 ，一个员工要离开楼 2 ，如果该请求列表可行，应该要有两个员工搬入楼 0 ，一个员工搬入楼 1 ，一个员工搬入楼 2 。

请你从原请求列表中选出若干个请求，使得它们是一个可行的请求列表，并返回所有可行列表中最大请求数目。

示例 1：

输入：n = 5, requests = [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]
输出：5
解释：请求列表如下：
从楼 0 离开的员工为 x 和 y ，且他们都想要搬到楼 1 。
从楼 1 离开的员工为 a 和 b ，且他们分别想要搬到楼 2 和 0 。
从楼 2 离开的员工为 z ，且他想要搬到楼 0 。
从楼 3 离开的员工为 c ，且他想要搬到楼 4 。
没有员工从楼 4 离开。
我们可以让 x 和 b 交换他们的楼，以满足他们的请求。
我们可以让 y，a 和 z 三人在三栋楼间交换位置，满足他们的要求。
所以最多可以满足 5 个请求。

示例 2：

输入：n = 3, requests = [[0,0],[1,2],[2,1]]
输出：3
解释：请求列表如下：
从楼 0 离开的员工为 x ，且他想要回到原来的楼 0 。
从楼 1 离开的员工为 y ，且他想要搬到楼 2 。
从楼 2 离开的员工为 z ，且他想要搬到楼 1 。
我们可以满足所有的请求。

示例 3：

输入：n = 4, requests = [[0,3],[3,1],[1,2],[2,0]]
输出：4

提示：

1 <= n <= 20
1 <= requests.length <= 16
requests[i].length == 2
0 <= from_i, to_i < n

lightbulb

解题思路

方法一：二进制枚举

我们注意到，换楼请求列表长度不超过 $16$ ，因此我们可以使用二进制枚举的方法枚举所有的换楼请求列表。具体地，我们可以使用一个长度为 $16$ 的二进制数来表示一种换楼请求列表，其中第 $i$ 位为 $1$ 表示第 $i$ 个换楼请求被选中，为 $0$ 表示第 $i$ 个换楼请求不被选中。

我们在 $[1, 2^{m})$ 的范围内枚举所有的二进制数，对于每个二进制数 $mask$ ，我们先算出它的二进制表示中有多少个 $1$ ，记为 $cnt$ ，如果 $cnt$ 比当前答案 $ans$ 大，那么我们再判断 $mask$ 是否是一个可行的换楼请求列表。如果是，那么我们就用 $cnt$ 更新答案 $ans$ 。判断 $mask$ 是否是一个可行的换楼请求列表，只需要判断对于每个楼，它的净流入量是否为 $0$ 即可。

时间复杂度 $O(2^m \times (m + n))$ ，空间复杂度 $O(n)$ 。其中 $m$ 和 $n$ 分别是换楼请求列表的长度和楼的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Solution:
    def maximumRequests(self, n: int, requests: List[List[int]]) -> int:
        def check(mask: int) -> bool:
            cnt = [0] * n
            for i, (f, t) in enumerate(requests):
                if mask >> i & 1:
                    cnt[f] -= 1
                    cnt[t] += 1
            return all(v == 0 for v in cnt)

        ans = 0
        for mask in range(1 << len(requests)):
            cnt = mask.bit_count()
            if ans < cnt and check(mask):
                ans = cnt
        return ans

speed

复杂度分析

指标	值
时间	O(2^(M * (M + N))
空间	O(N)

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of backtracking with pruning techniques.
question_mark
Candidate effectively utilizes bit manipulation for optimization.
question_mark
Candidate identifies early pruning conditions to limit unnecessary exploration.

warning

常见陷阱

外企场景

error
Failure to implement proper pruning leads to excessive exploration of infeasible branches.
error
Not optimizing state representation, which can lead to slow performance.
error
Overlooking the importance of checking net transfers early during the backtracking process.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider optimizing the pruning strategy to handle larger inputs.
arrow_right_alt
Explore dynamic programming approaches to compare with backtracking.
arrow_right_alt
Investigate greedy methods for approximate solutions in specific cases.

help

常见问题

外企场景

继续练习

#1863 找出所有子集的异或总和再求和 #2044 统计按位或能得到最大值的子集数目 #2151 基于陈述统计最多好人数