給你一個(gè)下標(biāo)從 0 開始的字符串?dāng)?shù)組 garbage ，其中 garbage[i] 表示第 i 個(gè)房子的垃圾集合。garbage[i] 只包含字符 ‘M’ ，‘P’ 和 ‘G’ ，但可能包含多個(gè)相同字符，每個(gè)字符分別表示一單位的金屬、紙和玻璃。垃圾車收拾 一 單位的任何一種垃圾都需要花費(fèi) 1 分鐘。

同時(shí)給你一個(gè)下標(biāo)從 0 開始的整數(shù)數(shù)組 travel ，其中 travel[i] 是垃圾車從房子 i 行駛到房子 i + 1 需要的分鐘數(shù)。

城市里總共有三輛垃圾車，分別收拾三種垃圾。每輛垃圾車都從房子 0 出發(fā)，按順序 到達(dá)每一棟房子。但它們 不是必須 到達(dá)所有的房子。

任何時(shí)刻只有 一輛 垃圾車處在使用狀態(tài)。當(dāng)一輛垃圾車在行駛或者收拾垃圾的時(shí)候，另外兩輛車 不能 做任何事情。

請你返回收拾完所有垃圾需要花費(fèi)的 最少 總分鐘數(shù)。

示例 1：

輸入：garbage = [“G”,“P”,“GP”,“GG”], travel = [2,4,3]
輸出：21
解釋：
收拾紙的垃圾車：

1. 從房子 0 行駛到房子 1
2. 收拾房子 1 的紙垃圾
3. 從房子 1 行駛到房子 2
4. 收拾房子 2 的紙垃圾
   收拾紙的垃圾車總共花費(fèi) 8 分鐘收拾完所有的紙垃圾。
   收拾玻璃的垃圾車：
5. 收拾房子 0 的玻璃垃圾
6. 從房子 0 行駛到房子 1
7. 從房子 1 行駛到房子 2
8. 收拾房子 2 的玻璃垃圾
9. 從房子 2 行駛到房子 3
10. 收拾房子 3 的玻璃垃圾
    收拾玻璃的垃圾車總共花費(fèi) 13 分鐘收拾完所有的玻璃垃圾。
    由于沒有金屬垃圾，收拾金屬的垃圾車不需要花費(fèi)任何時(shí)間。
    所以總共花費(fèi) 8 + 13 = 21 分鐘收拾完所有垃圾。

2 <= garbage.length <= 105
garbage[i] 只包含字母 ‘M’ ，‘P’ 和 ‘G’ 。
1 <= garbage[i].length <= 10
travel.length == garbage.length - 1
1 <= travel[i] <= 100

直接模擬即可：

class Solution {
public:int garbageCollection(vector<string>& garbage, vector<int>& travel) {int houseNum = garbage.size();int time = 0;int maxM = -1;int maxP = -1;int maxG = -1;for (int i = 0; i < houseNum; ++i) {for (char c : garbage[i]) {if (c == 'M') {maxM = i;} else if (c == 'P') {maxP = i;} else if (c == 'G') {maxG = i;}++time;}}for (int i = 0; i < houseNum - 1; ++i) {if (maxM > i) {time += travel[i];} if (maxP > i) {time += travel[i];}if (maxG > i) {time += travel[i];}}return time;}
};

如果有n個(gè)房子，此算法時(shí)間復(fù)雜度為O（n），空間復(fù)雜度為O（1）。