#2391
Minimum Amount of Time to Collect Garbage
pupil · 405 · lc medium +24 · verified · 85.1% accepted · 1,630 likes · top 96%
Description
An array garbage describes the garbage at each house as a string over the characters 'M', 'P', and 'G'. Three separate trucks collect metal ('M'), paper ('P'), and glass ('G') respectively.
You are also given a 0-indexed array travel where travel[i] is the travel time between houses i and i + 1. Each truck starts at house 0 and must collect every piece of its assigned garbage type in order. It takes one minute to collect each item of garbage and travel[i] minutes to drive between adjacent houses.
Return the total time for all three trucks to finish collecting all garbage.
Example 1:
Input: garbage = ["G","P","GP","GG"], travel = [2,4,3]
Output: 21
Explanation:
The paper garbage truck:
1. Travels from house 0 to house 1
2. Collects the paper garbage at house 1
3. Travels from house 1 to house 2
4. Collects the paper garbage at house 2
Altogether, it takes 8 minutes to pick up all the paper garbage.
The glass garbage truck:
1. Collects the glass garbage at house 0
2. Travels from house 0 to house 1
3. Travels from house 1 to house 2
4. Collects the glass garbage at house 2
5. Travels from house 2 to house 3
6. Collects the glass garbage at house 3
Altogether, it takes 13 minutes to pick up all the glass garbage.
Since there is no metal garbage, we do not need to consider the metal garbage truck.
Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.
Example 2:
Input: garbage = ["MMM","PGM","GP"], travel = [3,10]
Output: 37
Explanation:
The metal garbage truck takes 7 minutes to pick up all the metal garbage.
The paper garbage truck takes 15 minutes to pick up all the paper garbage.
The glass garbage truck takes 15 minutes to pick up all the glass garbage.
It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.
Code
1
2
3