2391. Minimum Amount of Time to Collect Garbage
你的城市有一大堆房子
房子里面有垃圾
垃圾一共分M, P, G三种
你有三台垃圾车分别能捡起M, P, G三种垃圾
垃圾车从0号房子开始
必须依照路线路过房子并捡起垃圾(0=>1=>2=>3)
但是无须经过所有房子
垃圾车每次能捡起一个垃圾
捡起一个垃圾须花费一分钟
从i号房子走到i+1号房子需花费travel[i]分钟
当有一台垃圾车运作的时候另外两台车禁止做任何事情
回传捡起所有垃圾最小花费的分钟数
Input: garbage = ["G","P","GP","GG"], travel = [2,4,3]
Output: 21
P垃圾车花费:2(走到1)+1(捡起垃圾)+4(走到2)+1(捡起垃圾)=8
G垃圾车花费:1(捡起垃圾)+2(走到1)+4(走到2)+1(捡起垃圾)+3(走到3)+2(捡起垃圾)=13
总花费:8+13=21
Input: garbage = ["MMM","PGM","GP"], travel = [3,10]
Output: 37
P垃圾车花费:15
G垃圾车花费:15
M垃圾车花费:7
总花费:15+15+7=37
Intuition:
三种垃圾不会互相影响
个别分开算加起来就好
Approach:
如果后面有垃圾
就继续往后走然后捡起来
所以我们先用一个变量cost记录他走路花费的时间
然后如果查到有垃圾就加到result
TS Code:
function takeGarbage (garbage: string[], travel: number[], garbageType:
string): number {
let result = 0
let cost = 0
for (let i = 0; i < garbage.length; i++) {
if (garbage[i].includes(garbageType)) {
result += cost
cost = 0
for (let j = 0; j < garbage[i].length; j++) {
if (garbage[i][j] === garbageType) result++
}
}
if (i < travel.length) cost += travel[i]
}
return result
}
function garbageCollection (garbage: string[], travel: number[]): number {
return takeGarbage(garbage, travel, "G") + takeGarbage(garbage, travel,
"P") + takeGarbage(garbage, travel, "M")
}