# 2391. Minimum Amount of Time to Collect Garbage
###### tags: `Leetcode` `Medium` `Simulation`
Link: https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/
## 思路
Observation 1:
"While one truck is driving or picking up garbage, the other two trucks cannot do anything."
**We can simply sum up the total running time for each truck,
they don't affect each other.**

Observation 2:
"Picking up one unit of any type of garbage takes 1 minute."
**We don't care how many units for each type,
we only care the total amount.**

Observation 3:
"however, they do not need to visit every house."
**We only care the position of the last garbage for each type**

我们只需要算出每一种垃圾的总数 每一种垃圾最后出现的位置 以及travel cost的prefix Sum就可以得到答案

## Code

class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
        int n = garbage.length;
        int[] prefixTravel = new int[n];
        for(int i=1; i<n; i++){
            prefixTravel[i] = prefixTravel[i-1]+travel[i-1];
        }
        int m=0, p=0, g=0;
        int mLast=0, pLast=0, gLast=0;
        for(int i=0; i<garbage.length; i++){
            String str = garbage[i];
            for(int j=0; j<str.length(); j++){
                if(str.charAt(j)=='M'){
                    m++;
                    mLast = i;
                }
                if(str.charAt(j)=='G'){
                    g++;
                    gLast = i;
                }
                if(str.charAt(j)=='P'){
                    p++;
                    pLast = i;
                }
            }
        }
        return prefixTravel[pLast]+prefixTravel[mLast]+prefixTravel[gLast]+m+p+g;
    }
}