Sponsored
Sponsored
The goal is to calculate the minimum time required for each truck to collect all the garbage of its type. A key observation is that the truck only needs to travel as far as the last house that has a specific kind of garbage. We use a prefix sum approach to calculate travel times efficiently. Each truck collects the garbage as it travels to each house that contains its type of garbage.
Time Complexity: O(n * m) where n is the number of houses and m is the average number of garbage types per house.
Space Complexity: O(1) aside from the input storage.
1#include <stdio.h>
2#include <string.h>
3
4int minTimeToCollectGarbage(char** garbage, int garbageSize, int* travel, int travelSize){
5 int time = 0;
6 int last[256] = {0};
7 int prefixSum[100001] = {0};
8
9 for (int i = 1; i < garbageSize; i++) {
10 prefixSum[i] = prefixSum[i - 1] + travel[i - 1];
11 }
12
13 for (int i = 0; i < garbageSize; i++) {
14 for (int j = 0; garbage[i][j]; j++) {
15 char g = garbage[i][j];
16 time++;
17 last[g] = i;
18 }
19 }
20
21 for (int i = 0; i < 256; i++) {
22 if (last[i]) {
23 time += prefixSum[last[i]];
24 }
25 }
26
27 return time;
28}
29
30int main() {
31 char* garbage[] = {"G", "P", "GP", "GG"};
32 int travel[] = {2, 4, 3};
33 int result = minTimeToCollectGarbage(garbage, 4, travel, 3);
34 printf("%d\n", result); // Output: 21
35 return 0;
36}This C implementation first calculates the prefix sum of travel times. It then iterates through each house, updating the last index for each type of garbage (using the ASCII code for 'M', 'P', 'G' as keys). At the end, it calculates the total time by adding the travel time up to the last house containing each type of garbage.
Instead of combining the travel times, here we individually compute the travel needed for each garbage type truck. This method essentially iterates through the garbage list and sums up the necessary travel times and garbage pickup times separately for 'M', 'P', and 'G'. Once that's done, the total represents the minimum time required.
Time Complexity: O(n * m) for each separate call, leading to overall O(3 * n * m).
Space Complexity: O(1) aside from input size.
1using System.Collections.Generic;
public class SolutionSep {
private int GetTime(List<string> garbage, List<int> travel, char type) {
int last = -1;
int time = 0;
for (int i = 0; i < garbage.Count; i++) {
string house = garbage[i];
foreach (char ch in house) {
if (ch == type) {
time++;
}
}
if (house.Contains(type)) {
if (i > 0 && last != -1) {
time += travel[last];
}
last = i - 1;
}
}
return time;
}
public int MinTimeToCollectGarbage(List<string> garbage, List<int> travel) {
return GetTime(garbage, travel, 'M') +
GetTime(garbage, travel, 'P') +
GetTime(garbage, travel, 'G');
}
public static void Main(string[] args) {
var garbage = new List<string> { "MMM", "PGM", "GP" };
var travel = new List<int> { 3, 10 };
SolutionSep sol = new SolutionSep();
Console.WriteLine(sol.MinTimeToCollectGarbage(garbage, travel)); // Output: 37
}
}This C# implementation, similar to others, defines a generic method for calculating the total operational time for each garbage truck type. It uses standard iteration and traversal of string lists to determine travel necessity and garbage count, looping over all potential truck types distinctly.