Minimum Amount of Time to Collect Garbage
Problem
Houses contain garbage of types M, P, G. Each truck (one per type) drives from house 0 and stops at the last house with that garbage; travel between houses i and i+1 takes travel[i]. Total time = total chars + sum of travel needed by each truck.
garbage = ["G","P","GP","GG"], travel = [2,4,3]21def garbage_collection(garbage, travel):
n = len(garbage)
prefix = [0] * n
for i in range(1, n):
prefix[i] = prefix[i - 1] + travel[i - 1]
last = {'M': 0, 'P': 0, 'G': 0}
total_chars = 0
for i, g in enumerate(garbage):
total_chars += len(g)
for c in g:
last[c] = i
return total_chars + prefix[last['M']] + prefix[last['P']] + prefix[last['G']]function garbageCollection(garbage, travel) {
const n = garbage.length;
const prefix = new Array(n).fill(0);
for (let i = 1; i < n; i++) prefix[i] = prefix[i - 1] + travel[i - 1];
const last = { M: 0, P: 0, G: 0 };
let total = 0;
for (let i = 0; i < n; i++) {
total += garbage[i].length;
for (const c of garbage[i]) last[c] = i;
}
return total + prefix[last.M] + prefix[last.P] + prefix[last.G];
}class Solution {
public int garbageCollection(String[] garbage, int[] travel) {
int n = garbage.length;
int[] prefix = new int[n];
for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + travel[i - 1];
int lm = 0, lp = 0, lg = 0, total = 0;
for (int i = 0; i < n; i++) {
total += garbage[i].length();
for (char c : garbage[i].toCharArray()) {
if (c == 'M') lm = i;
else if (c == 'P') lp = i;
else lg = i;
}
}
return total + prefix[lm] + prefix[lp] + prefix[lg];
}
}int garbageCollection(vector<string>& garbage, vector<int>& travel) {
int n = garbage.size();
vector<int> prefix(n, 0);
for (int i = 1; i < n; i++) prefix[i] = prefix[i - 1] + travel[i - 1];
int lm = 0, lp = 0, lg = 0, total = 0;
for (int i = 0; i < n; i++) {
total += (int)garbage[i].size();
for (char c : garbage[i]) {
if (c == 'M') lm = i;
else if (c == 'P') lp = i;
else lg = i;
}
}
return total + prefix[lm] + prefix[lp] + prefix[lg];
}Explanation
Total time splits cleanly into two pieces: the time spent picking up garbage and the time spent driving. Picking up is easy — each character is one unit, so we just add up the lengths of all the garbage strings.
The driving part is the clever bit. Each of the three trucks (M, P, G) starts at house 0 and only needs to drive as far as the last house that still has its type of garbage; going further would be wasted. So we record last['M'], last['P'], last['G'] as the farthest house index for each type.
To turn a house index into a driving cost we use a prefix sum of travel: prefix[i] is the total travel time from house 0 to house i. Then each truck's driving cost is simply prefix[last[type]], available in one lookup.
Example: garbage = ["G","P","GP","GG"], travel = [2,4,3]. Characters total 1+1+2+2 = 6. Prefix travels are 0,2,6,9. G last appears at house 3 (cost 9), P at house 2 (cost 6), M never (cost 0). Total 6 + 9 + 6 + 0 = 21.