Python实现最小化学生最大等待时间问题求解方案咨询

解题思路 #

要找到所有学生中最大等待时间的最小值，这是典型的二分查找应用场景：

1. 排序预处理：先将学生到达时间排序，便于后续分组判断。
2. 二分查找边界：左边界设为0（最小可能的等待时间），右边界设为排序后数组的最大时间差（最大可能的等待时间）。
3. 可行性检查：对于每个候选的最大等待时间mid，判断是否能用不超过M辆巴士安排所有学生，每辆巴士最多载C人，且车内所有学生的到达时间差不超过mid：
   • 从第一个学生开始，依次尝试将后续学生加入当前巴士，若满足时间差条件且未达容量限制则加入；否则启用新巴士。
   • 最终若所需巴士数≤M，说明mid可行，尝试更小的候选值；反之则需增大候选值。

Python代码实现 #

def find_min_max_wait_time(n, m, c, arr):
    arr.sort()
    left = 0
    right = arr[-1] - arr[0]
    
    while left < right:
        mid = (left + right) // 2
        buses = 1
        current_start = arr[0]
        count = 1
        
        for time in arr[1:]:
            if time - current_start <= mid and count < c:
                count += 1
            else:
                buses += 1
                current_start = time
                count = 1
                # 提前终止，若巴士数已超过m，无需继续遍历
                if buses > m:
                    break
        
        if buses <= m:
            right = mid
        else:
            left = mid + 1
    
    return left

# 示例测试
print(find_min_max_wait_time(4, 3, 3, [5, 3, 7, 8]))  # 输出1
print(find_min_max_wait_time(6, 1, 6, [1,1,1,1,1,1]))  # 输出0

代码说明 #

• 排序：确保我们可以按时间顺序处理学生，简化分组逻辑。
• 二分查找：通过不断缩小候选范围，高效找到最小的最大等待时间，时间复杂度为O(n log D)，其中D是最大时间差，远优于暴力枚举。
• 可行性检查：线性遍历学生数组，时间复杂度O(n)，保证整体效率。

内容的提问来源于stack exchange，提问作者yashshree patil