A班有的体育课上来了 𝑚 m 位男同学和 𝑛 n 位女同学,体育老师安排大家参加一项体育活动。 该活动要求同学们分成若干组,每组一位男同学,一位女同学,分组的要求是,同一组的男同学和女同学的身高差 ≤ 𝑇 ≤T。 请你编程计算出,按上述要求,同学们最多能分成多少组?
时间: 2024-12-28 17:32:26 浏览: 6
这个问题可以看作是一个二维区间匹配问题,目标是在满足身高差限制的前提下,最大化男女同学的配对数。为了找到最多的配对组合,我们可以使用滑动窗口策略。
首先,我们需要两个指针,一个 `male_ptr` 指向男生列表的开始,另一个 `female_ptr` 指向女生列表的开始。然后我们遍历男生列表,对于每个男生,检查当前男生的身高是否能满足与女生身高差不超过 `T` 的条件。如果是,我们就将女生移动到下一个,并增加一对配对(一组)。如果找不到符合条件的女生,就跳过这个男生并继续下一位。
代码示例(Python):
```python
def maxPairs(males, females, T):
males.sort()
females.sort()
male_ptr = 0
female_ptr = 0
pairs = 0
while male_ptr < len(males) and female_ptr < len(females):
if males[male_ptr] - females[female_ptr] <= T:
pairs += 1
male_ptr += 1
female_ptr += 1
else:
male_ptr += 1
return pairs
```
在这个函数中,`males` 和 `females` 分别是男生和女生的身高列表,返回的是最大配对数。
阅读全文