【LeetCode:2391. 收集垃圾的最少总时间 + 二分】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ 二分
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 💬 共勉

🚩 题目链接

2391. 收集垃圾的最少总时间

⛲ 题目描述

给你一个下标从 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 };
    }
}