TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2471,3 "name": "minimum_amount_of_time_to_collect_garbage",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/minimum-amount-of-time-to-collect-garbage/",6 "date": "1661040000000",7 "task_description": "You are given a **0-indexed** array of strings `garbage` where `garbage[i]` represents the assortment of garbage at the `ith` house. `garbage[i]` consists only of the characters `'M'`, `'P'` and `'G'` representing one unit of metal, paper and glass garbage respectively. Picking up **one** unit of any type of garbage takes `1` minute. You are also given a **0-indexed** integer array `travel` where `travel[i]` is the number of minutes needed to go from house `i` to house `i + 1`. There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house `0` and must visit each house **in order**; however, they do **not** need to visit every house. Only **one** garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks **cannot** do anything. Return_ the **minimum** number of minutes needed to pick up all the 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. ``` **Constraints:** `2 <= garbage.length <= 105` `garbage[i]` consists of only the letters `'M'`, `'P'`, and `'G'`. `1 <= garbage[i].length <= 10` `travel.length == garbage.length - 1` `1 <= travel[i] <= 100`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "garbage = [\"G\",\"P\",\"GP\",\"GG\"], travel = [2,4,3]",12 "output": "21 "13 },14 {15 "label": "Example 2",16 "input": "garbage = [\"MMM\",\"PGM\",\"GP\"], travel = [3,10]",17 "output": "37 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 [24 "GMPMGG",25 "PMMGM",26 "PMPPMMGGG",27 "MGPPPPGGG",28 "M",29 "MM",30 "MP",31 "PG",32 "GMGGGGMGG",33 "PMPMMGP",34 "PPGPMGGM",35 "PMM",36 "MGGPM",37 "MPPGMMGGMP",38 "MPMPPGMM",39 "MGMGPMG",40 "PGMGMGP",41 "GMPM",42 "MPMPPMMGG",43 "PMPMMMMGGP",44 "MPMPPMMGMP",45 "MGMMMGPMM",46 "M",47 "PGMMMMPPM",48 "MPP",49 "GGGMMPGMM",50 "MPGMMMMMGP",51 "PMM",52 "MPPGGG",53 "MPMP",54 "PGMGMGPM",55 "PMPGPMGGMM",56 "PGMMGPPMM",57 "PPGG",58 "GGP",59 "M",60 "GMMGMP",61 "M",62 "PMGP",63 "MMGPPPG",64 "P",65 "PMMPGGP",66 "PPMPGP"67 ],68 [69 81,70 84,71 97,72 196,73 236,74 294,75 358,76 444,77 521,78 549,79 627,80 655,81 656,82 714,83 722,84 723,85 757,86 798,87 801,88 827,89 872,90 890,91 946,92 974,93 1069,94 1156,95 1247,96 1328,97 1410,98 1486,99 1576,100 1626,101 1726,102 1804,103 1878,104 1917,105 1956,106 2055,107 2094,108 2192,109 2209,110 2231111 ]112 ],113 "output": 6947114 },115 {116 "input": [117 [118 "PG",119 "PMPMMPMPM",120 "MMPPGGPP",121 "MGGGMMP",122 "GPMMM",123 "G",124 "PGGP",125 "MMGPP",126 "P",127 "GPGMGMPGGP",128 "MMM",129 "MPP",130 "GP",131 "GP",132 "GPPPGMM",133 "PMPGMPPG",134 "G",135 "G",136 "GPMMPMMG",137 "P",138 "G",139 "GMG",140 "PGGMG",141 "PMPMGPGPGP",142 "GG",143 "PGG",144 "MMGMGPGPGP",145 "GGPGMGGMPP",146 "PMMPMGPGP",147 "PPGGGMPGP",148 "PPMMM",149 "MGPMPP",150 "MMPG",151 "MGMGPM",152 "GPMGPPPM",153 "MMG",154 "GP",155 "GGGPMPMG",156 "PPPGGPG",157 "MPPPMGMP",158 "PMMP",159 "GGPMGGPPM",160 "PPMMGPG",161 "MP",162 "MGMMGMG",163 "GPGGPPPGP",164 "MPGPPGGGM",165 "M",166 "MPPPMPPGM",167 "MPGP",168 "GPGGGP",169 "MPMGM",170 "PPMGMMMGPP",171 "PGP",172 "MM",173 "MMMM",174 "GPGMMMGG",175 "MGMGPMPG",176 "GG",177 "PMGPMM",178 "GPPMMGGGGG",179 "MMMGGG",180 "G",181 "MGGG",182 "GGPPGM",183 "MGGMGGGGM",184 "MPPPPGGPMM",185 "PMPMPM",186 "PMMGGPMP",187 "PGGG",188 "MPMGPPPP",189 "MGMM",190 "MPGPGPMPM",191 "MMMGM",192 "MPGPMMP",193 "GPPGGMM",194 "MGGGM",195 "MPGPGPPPMG",196 "GGPGGGG",197 "MMM",198 "MMMMG",199 "GMGPMPGMMG",200 "M",201 "PPGMMM"202 ],203 [204 12,205 49,206 72,207 155,208 255,209 262,210 263,211 276,212 354,213 394,214 491,215 585,216 590,217 668,218 732,219 748,220 824,221 857,222 894,223 937,224 1028,225 1095,226 1107,227 1167,228 1229,229 1328,230 1428,231 1524,232 1616,233 1716,234 1730,235 1828,236 1928,237 1963,238 2029,239 2117,240 2160,241 2218,242 2276,243 2361,244 2375,245 2440,246 2459,247 2513,248 2588,249 2649,250 2749,251 2793,252 2819,253 2865,254 2894,255 2928,256 2967,257 3025,258 3069,259 3128,260 3166,261 3266,262 3274,263 3318,264 3356,265 3379,266 3472,267 3551,268 3577,269 3620,270 3638,271 3693,272 3719,273 3731,274 3749,275 3779,276 3829,277 3838,278 3860,279 3893,280 3977,281 4057,282 4145,283 4209,284 4244,285 4301,286 4341287 ]288 ],289 "output": 13496290 },291 {292 "input": [293 [294 "MGPMMPGG",295 "MGMMGGM",296 "PGGGGPMGMM",297 "GMPPMPPPPM",298 "GPMPPPMPGP",299 "MGPGPM",300 "GGGMPGM",301 "MPPMPGP",302 "GMG",303 "PPPGPGMGPP",304 "MM",305 "MMMGMG",306 "GGGMPPPGGG",307 "PMMPMPMPM",308 "PPMMGPMGGG",309 "G",310 "MP",311 "PGPGPMG",312 "PPMPGGM",313 "MM",314 "MPPPMPGMP",315 "MGMMPP",316 "PMPM",317 "MPGGGGGGMM",318 "MGP",319 "P",320 "MGGPGGPMM",321 "PMGMMPGMGP",322 "MGGGGGP",323 "PGPMMGG",324 "GMP",325 "PPMGPMMGMP",326 "PMP",327 "MPPGGMM",328 "PGPPG",329 "MGGGPGMP",330 "GPGPP",331 "PG",332 "GMPPPGGGM",333 "GGGGPPGPGM",334 "GPPMPGPMM",335 "PMGGP",336 "PGMGPM",337 "GMMMMPM",338 "GMM",339 "GMMGGPM",340 "PGP",341 "MG",342 "MMMMMMGG",343 "PPMMMGM",344 "GPPPG",345 "PPGGPGPGP",346 "GGMGMP",347 "GMMMPPGPM",348 "MGP",349 "MGP",350 "MGMGMMMGM",351 "PMGGMGP",352 "GMGGP",353 "PMMMMPGM",354 "GPPP",355 "MMGPMMPMPM",356 "MGP",357 "MMMM",358 "PGM",359 "MGPMPMMPP",360 "MMGMPG",361 "PGMMPMGPMM",362 "GPPMGMMG",363 "MPG",364 "P",365 "MGPPMPGPG",366 "GPPMPGG",367 "GPMGM",368 "GPGGGPGPP"369 ],370 [371 23,372 123,373 147,374 157,375 188,376 287,377 348,378 441,379 459,380 531,381 559,382 579,383 665,384 686,385 693,386 724,387 746,388 792,389 868,390 884,391 906,392 971,393 990,394 1036,395 1090,396 1097,397 1168,398 1170,399 1201,400 1263,401 1339,402 1426,403 1485,404 1504,405 1537,406 1561,407 1606,408 1681,409 1684,410 1769,411 1838,412 1861,413 1891,414 1928,415 1994,416 2083,417 2168,418 2191,419 2228,420 2297,421 2389,422 2432,423 2440,424 2490,425 2579,426 2660,427 2734,428 2786,429 2849,430 2906,431 2935,432 3016,433 3069,434 3133,435 3207,436 3256,437 3259,438 3334,439 3392,440 3444,441 3462,442 3530,443 3610,444 3710445 ]446 ],447 "output": 11504448 },449 {450 "input": [451 [452 "GMPMPMPM",453 "PMM",454 "PPG",455 "PGMMPPMPMP",456 "GMM",457 "MGPPGPGPM",458 "PM",459 "PMGPP",460 "G",461 "MMGG",462 "P",463 "MPMMP",464 "PGMPPGPP",465 "MGMPGPMPP",466 "PMGMGMMMGM",467 "MMPGMGMMMM",468 "PGPPPMMMP",469 "GP",470 "PPM",471 "GPMMPG"472 ],473 [474 68,475 94,476 132,477 193,478 242,479 284,480 372,481 386,482 486,483 487,484 557,485 618,486 637,487 676,488 679,489 770,490 783,491 832,492 917493 ]494 ],495 "output": 2862496 },497 {498 "input": [499 [500 "PGGMPPGG",501 "GGMPPM",502 "PP",503 "MGMPMGG",504 "MGPGMMG",505 "MPPPMGG",506 "MPG",507 "PMPMG",508 "M",509 "MMMPGGMPGM",510 "GMMGPG",511 "GMGMM",512 "PP",513 "GMMPMPGMP",514 "MGGPGPGMG",515 "GMM",516 "MPGMMPM",517 "MMPGMGPPMG",518 "PPPMGPMMG",519 "M",520 "MGGGMGM",521 "GP",522 "GMMPG",523 "MPPPPG",524 "PGPPGGG",525 "GMP",526 "PPGGPMGP",527 "MGGGMP",528 "M",529 "P",530 "MGMG",531 "MMPMGGMMM",532 "GGMM",533 "GPGGMPPMGG",534 "PG",535 "PGGG",536 "GPMGPP",537 "PG",538 "PPPGMMPGP",539 "PGPPPMGG",540 "PGM",541 "GMMPMGMPGP",542 "PGMPGPPG",543 "MGG",544 "PGMPG",545 "MPMPGGGMM",546 "PMMGPP",547 "G",548 "MGGM",549 "P",550 "MGGPMGPG",551 "GM",552 "GMPMMPM",553 "GGGGMGM",554 "PPGGPPGM",555 "PGMPMMM",556 "PPGGM",557 "GGGM",558 "PPGGMGPPM",559 "P",560 "PPGMPMGPPG",561 "MPMMGGGGP",562 "MGPGM",563 "MMPMGGGMMP",564 "GMPM",565 "GGG",566 "MMMG",567 "GPGGMPGMP",568 "PPP",569 "MGMPM",570 "MGMPGMMPG"571 ],572 [573 18,574 48,575 135,576 198,577 282,578 327,579 331,580 431,581 498,582 540,583 548,584 613,585 696,586 751,587 820,588 852,589 893,590 936,591 1004,592 1079,593 1172,594 1227,595 1259,596 1312,597 1380,598 1443,599 1486,600 1488,601 1518,602 1613,603 1678,604 1762,605 1765,606 1786,607 1844,608 1875,609 1878,610 1915,611 1927,612 1928,613 1944,614 2010,615 2107,616 2146,617 2172,618 2207,619 2274,620 2365,621 2369,622 2405,623 2465,624 2543,625 2634,626 2732,627 2819,628 2917,629 2985,630 3023,631 3034,632 3104,633 3204,634 3259,635 3346,636 3359,637 3385,638 3386,639 3464,640 3510,641 3604,642 3686643 ]644 ],645 "output": 11458646 },647 {648 "input": [649 [650 "M",651 "PMGGPGGGMP",652 "GGMGPM",653 "GMGPPGPGMM",654 "MGG",655 "PGPP",656 "PPPM",657 "GPGPG",658 "PMMPPPPG",659 "MMPGGPP",660 "PGGPPMP",661 "MM",662 "PPPG",663 "MPPM",664 "G",665 "GMMMPGMMPG",666 "M",667 "P",668 "GPPP",669 "PMG",670 "PMPGGGP",671 "M",672 "GPGGPMPP",673 "GM",674 "PGMGPPMP",675 "PGGGMGPMG",676 "MGPM",677 "MMMMGPMPMG",678 "MPMPPP",679 "MP",680 "MMGPMPMMPG",681 "MMGPGPPPPM",682 "GPMPMG",683 "PP",684 "MPMG"685 ],686 [687 41,688 138,689 207,690 212,691 289,692 333,693 409,694 475,695 574,696 659,697 696,698 760,699 808,700 872,701 972,702 1056,703 1134,704 1222,705 1276,706 1360,707 1452,708 1510,709 1532,710 1592,711 1610,712 1695,713 1717,714 1734,715 1766,716 1859,717 1943,718 1950,719 2047,720 2113721 ]722 ],723 "output": 6523724 },725 {726 "input": [727 [728 "GMMMP",729 "G",730 "GGPGGMGMPG",731 "GMMM",732 "GGP",733 "PMP",734 "M",735 "GPPGGPP",736 "PMGPPMP",737 "MMM",738 "P",739 "MMG",740 "GMPGGM",741 "P",742 "PGGGGPG",743 "GPPPPMMPGP",744 "PPG",745 "PMGP",746 "PGMMP",747 "GMPG",748 "MMP",749 "MPMMGMMM",750 "PMGGPGP",751 "GPPPMP",752 "G",753 "GGMGP",754 "GGMGMGP",755 "GGPMP",756 "PGMP",757 "MGMPMG",758 "MPPG",759 "PPGPGPMP",760 "PM",761 "MGPGGG",762 "GPPPG",763 "GPGPP",764 "MGMMPGG",765 "MPMGPPM",766 "GGMMGMMM",767 "MGMPGM",768 "GMMMMPP",769 "P",770 "MP",771 "MMPGGPPMP",772 "MPP",773 "MPMPPGGPM",774 "PM",775 "P",776 "PPMGGP",777 "P",778 "MPGPGPMM",779 "MM",780 "G",781 "PPGPPMGG",782 "MP",783 "GMPG",784 "MGGGGMMGGP",785 "M",786 "MPPP",787 "GGGMMG",788 "PMPM",789 "GMPPMGPGG",790 "PPMGG",791 "MP",792 "MGGGPP",793 "MMMGMGG",794 "MMPMGM",795 "P",796 "GMPMMMGMP",797 "GPPMMMMGMM",798 "MPGPPP",799 "MMG",800 "PPPMP",801 "GGMGPMGGMP",802 "PMMGGGGGG",803 "GGGGGGPGG",804 "MMMMPM",805 "GPMGPPMMPG",806 "G",807 "MMGPMM",808 "GG",809 "PMGMPGMPM",810 "MGM",811 "PGMPMPGMG",812 "M",813 "MGPGGGM",814 "MGMMPPG",815 "GGPPMPGP",816 "G",817 "GMPM",818 "PPPGMMMPP",819 "MPMPPPGPP",820 "PGP",821 "GPGPMGGG",822 "GMMMMGGP",823 "GMMGPGPM",824 "MG",825 "M",826 "MP"827 ],828 [829 85,830 162,831 210,832 278,833 330,834 413,835 418,836 480,837 542,838 607,839 638,840 654,841 731,842 768,843 777,844 787,845 806,846 844,847 876,848 912,849 939,850 942,851 988,852 1085,853 1134,854 1147,855 1240,856 1261,857 1312,858 1362,859 1435,860 1456,861 1477,862 1542,863 1543,864 1559,865 1562,866 1588,867 1648,868 1705,869 1760,870 1764,871 1837,872 1888,873 1951,874 1952,875 2039,876 2077,877 2177,878 2246,879 2249,880 2286,881 2311,882 2314,883 2414,884 2473,885 2545,886 2564,887 2565,888 2665,889 2714,890 2744,891 2841,892 2845,893 2916,894 2974,895 3041,896 3101,897 3141,898 3228,899 3258,900 3299,901 3327,902 3378,903 3445,904 3457,905 3530,906 3629,907 3718,908 3744,909 3781,910 3818,911 3831,912 3841,913 3914,914 3946,915 3964,916 4022,917 4043,918 4112,919 4153,920 4199,921 4240,922 4246,923 4342,924 4380,925 4444,926 4493927 ]928 ],929 "output": 13876930 },931 {932 "input": [933 [934 "PGGGPGMMMG",935 "MGPGPGPP",936 "PMMMGMMG",937 "PPPGPP",938 "PGPMPGGM",939 "MPMMGMMPG",940 "GPGMPMPP",941 "P",942 "GM",943 "PGGMGPPMP",944 "GMPMG",945 "P",946 "P",947 "MGGPGG",948 "PMMMPGGPMG",949 "MGPPM",950 "P",951 "PGPMMMMGG",952 "PM",953 "GGG",954 "MP",955 "PPGGG",956 "PM",957 "PGMPMGPGP",958 "GGPGGMP",959 "GGMGGMGMG",960 "PM",961 "PG",962 "MPG",963 "GGPGM"964 ],965 [966 75,967 148,968 183,969 193,970 207,971 283,972 289,973 376,974 381,975 456,976 508,977 601,978 631,979 723,980 798,981 837,982 911,983 933,984 934,985 941,986 1028,987 1035,988 1082,989 1131,990 1192,991 1256,992 1301,993 1333,994 1357995 ]996 ],997 "output": 4229998 },999 {1000 "input": [1001 [1002 "GP",1003 "GMGPGMMGM",1004 "PGGP",1005 "MPMPMPPGMP",1006 "PGPGMGPMM",1007 "GPGPPPG",1008 "MMMPPPPMPM",1009 "GGMP",1010 "MPMM",1011 "GGGMGMM",1012 "PGPGPMPMG",1013 "GGMMPPMGPG",1014 "PMGP",1015 "GGPGMMG",1016 "PGGG",1017 "MGMMM",1018 "GMGM",1019 "GGGGMPGMMG",1020 "PPPGGGG",1021 "GGP",1022 "GGP",1023 "GMG",1024 "PM",1025 "PGGMGPPGPM",1026 "PPPMPPPP",1027 "MMMMMP",1028 "MGPMPGPP",1029 "PP",1030 "GP",1031 "MMPMMPPG",1032 "MMGPGMPMMP",1033 "GGPMPPGMG",1034 "GGMM",1035 "GMPMM",1036 "GGPPGMGPG",1037 "PMM",1038 "GPGGGPMGG",1039 "MPMGGGGG",1040 "MMMPMMGMMM",1041 "PMGPPPMPGP",1042 "GPPMP",1043 "GP",1044 "MGGM",1045 "PPGMPG",1046 "GGPGPMP",1047 "GMMPGPGGP",1048 "GMMPGPMGP",1049 "GMGMP",1050 "PP",1051 "GPGGPMPM",1052 "PPPM",1053 "MPGMGMM",1054 "GMGMG",1055 "GPGGMMPPGG",1056 "PMPGMPPMP",1057 "PMPMPGGP",1058 "PPMPGM",1059 "MGPPM",1060 "PMMPPPPGP",1061 "PPGMG",1062 "PGPPMMGGMM",1063 "MMG",1064 "GMGMPGPMPM",1065 "PMPMM",1066 "PPPMMGPMP",1067 "MG"1068 ],1069 [1070 1,1071 22,1072 106,1073 165,1074 214,1075 288,1076 328,1077 391,1078 395,1079 429,1080 451,1081 529,1082 618,1083 688,1084 756,1085 845,1086 889,1087 953,1088 1006,1089 1062,1090 1136,1091 1138,1092 1177,1093 1272,1094 1341,1095 1429,1096 1459,1097 1462,1098 1522,1099 1571,1100 1582,1101 1655,1102 1686,1103 1702,1104 1710,1105 1803,1106 1898,1107 1923,1108 2015,1109 2049,1110 2132,1111 2189,1112 2214,1113 2227,1114 2229,1115 2263,1116 2330,1117 2349,1118 2399,1119 2436,1120 2532,1121 2620,1122 2705,1123 2746,1124 2842,1125 2893,1126 2979,1127 3031,1128 3129,1129 3186,1130 3283,1131 3343,1132 3369,1133 3391,1134 34751135 ]1136 ],1137 "output": 107631138 },1139 {1140 "input": [1141 [1142 "PMPMPPP",1143 "G",1144 "MPMG",1145 "GPPMMG",1146 "GMGPGMMPGM",1147 "PGP",1148 "GMGPPGG",1149 "PPPPGGP",1150 "MMP",1151 "GGGMG",1152 "GGMPMPPGG",1153 "G",1154 "MMGM",1155 "M",1156 "P",1157 "GM",1158 "MMPGGPMPPG",1159 "GMGPP",1160 "GPPP",1161 "PGMM",1162 "PGMMPMGP",1163 "GMMMG",1164 "PPPPMGGM",1165 "PGMGGPG",1166 "MGMG",1167 "MMMMPPMG",1168 "MMPMPPPGPG",1169 "MGPG",1170 "PMGM",1171 "MG",1172 "M",1173 "GG",1174 "GM",1175 "GMP"1176 ],1177 [1178 22,1179 29,1180 38,1181 138,1182 172,1183 268,1184 316,1185 363,1186 384,1187 400,1188 433,1189 489,1190 523,1191 563,1192 632,1193 671,1194 684,1195 773,1196 844,1197 944,1198 982,1199 1028,1200 1068,