🚩 题目链接
⛲ 题目描述
给你一个下标从 0 开始的字符串数组 garbage ，其中 garbage[i] 表示第 i 个房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ，‘P’ 和 ‘G’ ，但可能包含多个相同字符，每个字符分别表示一单位的金属、纸和玻璃。垃圾车收拾 一 单位的任何一种垃圾都需要花费 1 分钟。
同时给你一个下标从 0 开始的整数数组 travel ，其中 travel[i] 是垃圾车从房子 i 行驶到房子 i + 1 需要的分钟数。
城市里总共有三辆垃圾车，分别收拾三种垃圾。每辆垃圾车都从房子 0 出发，按顺序 到达每一栋房子。但它们 不是必须 到达所有的房子。
任何时刻只有 一辆 垃圾车处在使用状态。当一辆垃圾车在行驶或者收拾垃圾的时候，另外两辆车 不能 做任何事情。
请你返回收拾完所有垃圾需要花费的 最少 总分钟数。
示例 1：
输入：garbage = [“G”,“P”,“GP”,“GG”], travel = [2,4,3]
输出：21
解释：
收拾纸的垃圾车：
- 从房子 0 行驶到房子 1
- 收拾房子 1 的纸垃圾
- 从房子 1 行驶到房子 2
- 收拾房子 2 的纸垃圾
收拾纸的垃圾车总共花费 8 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车：
- 收拾房子 0 的玻璃垃圾
- 从房子 0 行驶到房子 1
- 从房子 1 行驶到房子 2
- 收拾房子 2 的玻璃垃圾
- 从房子 2 行驶到房子 3
- 收拾房子 3 的玻璃垃圾
收拾玻璃的垃圾车总共花费 13 分钟收拾完所有的玻璃垃圾。
由于没有金属垃圾，收拾金属的垃圾车不需要花费任何时间。
所以总共花费 8 + 13 = 21 分钟收拾完所有垃圾。
示例 2：
输入：garbage = [“MMM”,“PGM”,“GP”], travel = [3,10]
输出：37
解释：
收拾金属的垃圾车花费 7 分钟收拾完所有的金属垃圾。
收拾纸的垃圾车花费 15 分钟收拾完所有的纸垃圾。
收拾玻璃的垃圾车花费 15 分钟收拾完所有的玻璃垃圾。
总共花费 7 + 15 + 15 = 37 分钟收拾完所有的垃圾。
提示：
2 <= garbage.length <= 105
garbage[i] 只包含字母 ‘M’ ，‘P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100
🌟 求解思路&实现代码&运行结果
⚡ 二分
🥦 求解思路
- 该题目我们通过二分来求解，每次我们来二分时间，判断此时的时间是否满足要求，如果满足，右边界左移，反之，左边界右移。
- 那怎么判断呢？首先我们需要找到专门收集对应的垃圾最后的位置，记录并返回。
- 然后去模拟计算每一辆垃圾车去i到i+1位置过程的时间；
- 注意，收集垃圾的过程，我们最后直接统一计算即可。
- 有了基本的思路，接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {
public int garbageCollection(String[] garbage, int[] travel) {
int sum = 0;
for (int v : travel)
sum += v;
sum *= 10;
int left = -1, right = sum + 1;
while (left + 1 < right) {
int mid = left + right >> 1;
if (check(mid, garbage, travel)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int mid, String[] garbage, int[] travel) {
int n = garbage.length;
int time = 0;
int[] lastIndex = findLastIndex(garbage);
for (int index = 0; index < lastIndex.length; index++) {
int idx = lastIndex[index];
if (idx == -1)
continue;
for (int i = 0; i < idx; i++) {
time += travel[i];
}
}
for (int i = 0; i < n; i++) {
time += garbage[i].length();
}
return time <= mid;
}
private int[] findLastIndex(String[] garbage) {
int n = garbage.length;
int index1 = -1, index2 = -1, index3 = -1;
for (int i = 0; i < n; i++) {
if (garbage[i].contains("G")) {
index1 = i;
}
if (garbage[i].contains("P")) {
index2 = i;
}
if (garbage[i].contains("M")) {
index3 = i;
}
}
return new int[] { index1, index2, index3 };
}
}