3733. 完成所有配送的最短时间

Medium

题目描述

给你两个大小为 2 的整数数组：d = [d1, d2] 和 r = [r1, r2]。

有两架配送无人机需要完成特定数量的配送任务。无人机 i 必须完成 di 次配送。

每次配送恰好需要一小时，并且在任何给定的小时内只有一架无人机可以进行配送。

此外，两架无人机都需要在特定间隔进行充电，充电期间无法进行配送。无人机 i 必须每 ri 小时充电一次（即在 ri 的倍数小时充电）。

返回一个整数，表示完成所有配送所需的最少总时间（小时）。

示例 1：

输入：d = [3,1], r = [2,3]
输出：5
解释：
第一架无人机在第 1、3、5 小时配送（在第 2、4 小时充电）。
第二架无人机在第 2 小时配送（在第 3 小时充电）。

示例 2：

输入：d = [1,3], r = [2,2]
输出：7
解释：
第一架无人机在第 3 小时配送（在第 2、4、6 小时充电）。
第二架无人机在第 1、5、7 小时配送（在第 2、4、6 小时充电）。

示例 3：

输入：d = [2,1], r = [3,4]
输出：3
解释：
第一架无人机在第 1、2 小时配送（在第 3 小时充电）。
第二架无人机在第 3 小时配送。

约束条件：

d = [d1, d2]
1 <= di <= 10^9
r = [r1, r2]
2 <= ri <= 3 * 10^4

解题思路

这道题的核心在于计算在给定时间 T 内，两架无人机能够完成的最大配送次数是否满足要求。

思路分析：

二分搜索时间：由于时间具有单调性（时间越长，能完成的配送越多），可以用二分搜索找到最小的总时间 T。
计算可用工作时间：
- 无人机 i 在时间 T 内需要充电 floor(T/ri) 次
- 无人机 i 的可用工作时间：c_i = T - floor(T/ri)
- 两架无人机同时充电的时间：floor(T/lcm(r1,r2))
工作时间分配策略：
- 每架无人机都有独占的工作时间（另一架在充电时）
- 还有共享的工作时间（两架都可以工作）
- 独占时间 = 总可用时间 - 共享时间
- 共享时间 = T - 总充电时间 + 重叠充电时间
可行性检验：
- 先让每架无人机利用独占时间完成配送
- 剩余的配送任务必须能在共享时间内完成

算法流程：

二分搜索答案范围 [1, sum(d) + max_recharge_time]
对于每个候选时间 T，计算是否能完成所有配送
返回满足条件的最小时间

代码实现

class Solution {
public:
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
    
    bool canComplete(vector<int>& d, vector<int>& r, long long T) {
        long long r1 = r[0], r2 = r[1];
        long long d1 = d[0], d2 = d[1];
        
        // 计算各自的可用工作时间
        long long c1 = T - T / r1;  // 无人机1的工作时间
        long long c2 = T - T / r2;  // 无人机2的工作时间
        
        // 计算共享工作时间（两架都可以工作的时间）
        long long lcm_r = lcm(r1, r2);
        long long shared = T - T / r1 - T / r2 + T / lcm_r;
        
        // 计算独占时间
        long long exclusive1 = c1 - shared;  // 无人机1独占时间
        long long exclusive2 = c2 - shared;  // 无人机2独占时间
        
        // 先用独占时间完成配送
        long long remaining1 = max(0LL, d1 - exclusive1);
        long long remaining2 = max(0LL, d2 - exclusive2);
        
        // 检查剩余配送是否能在共享时间内完成
        return remaining1 + remaining2 <= shared;
    }
    
    long long minimumTime(vector<int>& d, vector<int>& r) {
        long long left = 1, right = (long long)d[0] + d[1] + max(r[0], r[1]);
        
        while (left < right) {
            long long mid = left + (right - left) / 2;
            if (canComplete(d, r, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
};

class Solution:
    def minimumTime(self, d: List[int], r: List[int]) -> int:
        def gcd(a, b):
            while b:
                a, b = b, a % b
            return a
        
        def lcm(a, b):
            return a * b // gcd(a, b)
        
        def canComplete(T):
            r1, r2 = r[0], r[1]
            d1, d2 = d[0], d[1]
            
            # 计算各自的可用工作时间
            c1 = T - T // r1
            c2 = T - T // r2
            
            # 计算共享工作时间
            lcm_r = lcm(r1, r2)
            shared = T - T // r1 - T // r2 + T // lcm_r
            
            # 计算独占时间
            exclusive1 = c1 - shared
            exclusive2 = c2 - shared
            
            # 先用独占时间完成配送
            remaining1 = max(0, d1 - exclusive1)
            remaining2 = max(0, d2 - exclusive2)
            
            # 检查剩余配送是否能在共享时间内完成
            return remaining1 + remaining2 <= shared
        
        left, right = 1, sum(d) + max(r)
        
        while left < right:
            mid = (left + right) // 2
            if canComplete(mid):
                right = mid
            else:
                left = mid + 1
        
        return left

public class Solution {
    private long Gcd(long a, long b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private long Lcm(long a, long b) {
        return a / Gcd(a, b) * b;
    }
    
    private bool CanComplete(int[] d, int[] r, long T) {
        long r1 = r[0], r2 = r[1];
        long d1 = d[0], d2 = d[1];
        
        // 计算各自的可用工作时间
        long c1 = T - T / r1;
        long c2 = T - T / r2;
        
        // 计算共享工作时间
        long lcmR = Lcm(r1, r2);
        long shared = T - T / r1 - T / r2 + T / lcmR;
        
        // 计算独占时间
        long exclusive1 = c1 - shared;
        long exclusive2 = c2 - shared;
        
        // 先用独占时间完成配送
        long remaining1 = Math.Max(0, d1 - exclusive1);
        long remaining2 = Math.Max(0, d2 - exclusive2);
        
        // 检查剩余配送是否能在共享时间内完成
        return remaining1 + remaining2 <= shared;
    }
    
    public long MinimumTime(int[] d, int[] r) {
        long left = 1;
        long right = (long)d[0] + d[1] + Math.Max(r[0], r[1]);
        
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (CanComplete(d, r, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

var minimumTime = function(d, r) {
    function canComplete(time, d, r) {
        let deliveries1 = 0;
        let deliveries2 = 0;
        
        for (let hour = 1; hour <= time; hour++) {
            if (hour % r[0] !== 0) {
                deliveries1++;
            } else if (hour % r[1] !== 0) {
                deliveries2++;
            }
        }
        
        if (deliveries1 >= d[0] && deliveries2 >= d[1]) return true;
        
        deliveries1 = 0;
        deliveries2 = 0;
        
        for (let hour = 1; hour <= time; hour++) {
            if (hour % r[1] !== 0) {
                deliveries2++;
            } else if (hour % r[0] !== 0) {
                deliveries1++;
            }
        }
        
        return deliveries1 >= d[0] && deliveries2 >= d[1];
    }
    
    let left = 1;
    let right = (d[0] + d[1]) * Math.max(r[0], r[1]);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canComplete(mid, d, r)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(log(d1+d2) * log(max(r1,r2)))
空间复杂度	O(1)

说明：

二分搜索的范围是 O(d1+d2)，每次搜索需要 O(log(max(r1,r2))) 时间计算 LCM
空间复杂度为常数级别，只使用了固定的额外变量

题目描述#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

代码实现

复杂度分析