求解A组人员全部匹配B组固定成员的最短时间最优算法

针对你提出的问题，暴力枚举所有匹配组合的时间复杂度是O(C(m,n)*n)，当A、B组人数较多时效率极低，有两种远优于暴力的解法：

解法1：二分答案+贪心验证（推荐） #

时间复杂度为O((n+m)logD)，其中n为A组人数、m为B组人数，D为数轴上最大的坐标差。

核心思路 #

我们的目标是找到最小的时间T，使得所有A组人员都能在T秒内匹配到不重复的B组人员。T的取值范围是固定的[0, D]，可以通过二分法快速缩小候选范围，每次只需要验证当前T是否满足匹配要求即可。

验证规则（贪心策略） #

1. 先将A组和B组的坐标都按从小到大排序
2. 初始化两个指针i（指向当前待匹配的A组成员，从0开始）、j（指向当前待分配的B组成员，从0开始）
3. 遍历过程：
   • 若当前|A[i] - B[j]| ≤ T，说明两个可以匹配，i和j都后移一位（B组成员不可重复使用）
   • 若B[j] < A[i] - T，说明当前B组成员位置太小，无法匹配任何剩下的A组成员（因为A已经排序，后面的A位置更大），j后移一位
   • 若B[j] > A[i] + T，说明当前T太小，无法给A[i]找到匹配，直接判定当前T不可行
4. 遍历结束后如果所有A组成员都完成匹配（i == n），则当前T可行，可以尝试更小的T，否则需要增大T。

示例验证 #

你给出的用例排序后A=[5,7,8]，B=[2,3,4,9]，验证T=3：

• i=0（A=5），j=0（B=2）：|5-2|=3≤3，匹配成功，i=1，j=1
• i=1（A=7），j=1（B=3）：7-3=4>3，j后移到2（B=4），|7-4|=3≤3，匹配成功，i=2，j=3
• i=2（A=8），j=3（B=9）：|8-9|=1≤3，匹配成功，i=3==n=3，验证通过

解法2：动态规划 #

适合数据量较小的场景，时间复杂度O(n*m)。

1. 先排序A、B组坐标
2. 定义dp[i][j]为前i个A组成员匹配前j个B组成员的最小最大移动时间
3. 转移方程：dp[i][j] = min( dp[i][j-1], max( dp[i-1][j-1], abs(A[i-1] - B[j-1]) ) )，含义是要么第j个B组成员不参与匹配，取前j-1个的结果；要么第i个A匹配第j个B，取前i-1个A匹配前j-1个B的最大时间和当前匹配移动时间的最大值，两种情况取更优的结果。
4. 边界条件：dp[0][j] = 0（0个A不需要匹配时间），dp[i][0] = 无穷大（0个B无法匹配i个A）

内容的提问来源于stack exchange，提问作者Gordon Z