FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 2642,3 "name": "time_to_cross_a_bridge",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/time-to-cross-a-bridge/",6 "date": "2023-01-01 00:00:00",7 "task_description": "There are `k` workers who want to move `n` boxes from the right (old) warehouse to the left (new) warehouse. You are given the two integers `n` and `k`, and a 2D integer array `time` of size `k x 4` where `time[i] = [righti, picki, lefti, puti]`. The warehouses are separated by a river and connected by a bridge. Initially, all `k` workers are waiting on the left side of the bridge. To move the boxes, the `ith` worker can do the following: Cross the bridge to the right side in `righti` minutes. Pick a box from the right warehouse in `picki` minutes. Cross the bridge to the left side in `lefti` minutes. Put the box into the left warehouse in `puti` minutes. The `ith` worker is **less efficient** than the j`th` worker if either condition is met: `lefti + righti > leftj + rightj` `lefti + righti == leftj + rightj` and `i > j` The following rules regulate the movement of the workers through the bridge: Only one worker can use the bridge at a time. When the bridge is unused prioritize the **least efficient** worker (who have picked up the box) on the right side to cross. If not, prioritize the **least efficient** worker on the left side to cross. If enough workers have already been dispatched from the left side to pick up all the remaining boxes, **no more** workers will be sent from the left side. Return the **elapsed minutes** at which the last box reaches the **left side of the bridge**. **Example 1:** **Input:** n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]] **Output:** 6 **Explanation:** ``` From 0 to 1 minutes: worker 2 crosses the bridge to the right. From 1 to 2 minutes: worker 2 picks up a box from the right warehouse. From 2 to 6 minutes: worker 2 crosses the bridge to the left. From 6 to 7 minutes: worker 2 puts a box at the left warehouse. The whole process ends after 7 minutes. We return 6 because the problem asks for the instance of time at which the last worker reaches the left side of the bridge. ``` **Example 2:** **Input:** n = 3, k = 2, time = [[1,5,1,8],[10,10,10,10]] **Output:** 37 **Explanation:** ``` ``` The last box reaches the left side at 37 seconds. Notice, how we **do not** put the last boxes down, as that would take more time, and they are already on the left with the workers. **Constraints:** `1 <= n, k <= 104` `time.length == k` `time[i].length == 4` `1 <= lefti, picki, righti, puti <= 1000`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 1, k = 3, time = [[1,1,2,1],[1,1,3,1],[1,1,4,1]]",12 "output": "6 "13 },14 {15 "label": "Example 2",16 "input": "n = 3, k = 2, time = [[1,5,1,8],[10,10,10,10]]",17 "output": "37 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 1868,24 3681,25 [26 [27 462,28 97,29 714,30 56231 ],32 [33 763,34 818,35 385,36 6837 ],38 [39 42,40 747,41 112,42 50243 ],44 [45 901,46 31,47 357,48 73749 ],50 [51 160,52 578,53 766,54 99555 ],56 [57 140,58 886,59 16,60 4961 ],62 [63 19,64 828,65 283,66 34067 ],68 [69 76,70 848,71 834,72 64973 ],74 [75 834,76 204,77 561,78 97579 ],80 [81 877,82 591,83 274,84 93885 ],86 [87 705,88 840,89 392,90 53191 ],92 [93 130,94 818,95 752,96 10897 ],98 [99 574,100 628,101 435,102 565103 ],104 [105 14,106 168,107 544,108 42109 ],110 [111 248,112 619,113 176,114 471115 ],116 [117 189,118 628,119 688,120 530121 ],122 [123 866,124 220,125 657,126 806127 ],128 [129 33,130 968,131 410,132 301133 ],134 [135 111,136 684,137 795,138 620139 ],140 [141 836,142 177,143 493,144 728145 ],146 [147 841,148 513,149 289,150 897151 ],152 [153 964,154 292,155 872,156 780157 ],158 [159 936,160 496,161 725,162 65163 ],164 [165 316,166 484,167 429,168 297169 ],170 [171 924,172 393,173 537,174 21175 ],176 [177 647,178 465,179 933,180 382181 ],182 [183 195,184 879,185 827,186 206187 ],188 [189 454,190 78,191 535,192 668193 ],194 [195 611,196 653,197 990,198 973199 ],200 [201 51,202 883,203 390,204 113205 ],206 [207 96,208 656,209 924,210 472211 ],212 [213 787,214 515,215 15,216 24217 ],218 [219 125,220 167,221 854,222 705223 ],224 [225 332,226 686,227 164,228 219229 ],230 [231 200,232 206,233 650,234 23235 ],236 [237 365,238 563,239 654,240 860241 ],242 [243 134,244 809,245 145,246 218247 ],248 [249 190,250 333,251 779,252 67253 ],254 [255 50,256 546,257 467,258 237259 ],260 [261 45,262 371,263 855,264 339265 ],266 [267 103,268 161,269 977,270 882271 ],272 [273 363,274 733,275 215,276 75277 ],278 [279 940,280 569,281 474,282 616283 ],284 [285 53,286 273,287 100,288 279289 ],290 [291 996,292 139,293 240,294 279295 ],296 [297 298,298 51,299 609,300 494301 ],302 [303 113,304 641,305 513,306 521307 ],308 [309 406,310 433,311 924,312 804313 ],314 [315 496,316 981,317 521,318 214319 ],320 [321 233,322 858,323 351,324 133325 ],326 [327 2,328 287,329 436,330 365331 ],332 [333 274,334 718,335 206,336 865337 ],338 [339 623,340 695,341 247,342 314343 ],344 [345 35,346 29,347 956,348 304349 ],350 [351 793,352 310,353 496,354 801355 ],356 [357 825,358 94,359 64,360 517361 ],362 [363 654,364 35,365 298,366 591367 ],368 [369 342,370 301,371 143,372 107373 ],374 [375 603,376 334,377 537,378 25379 ],380 [381 812,382 955,383 659,384 170385 ],386 [387 390,388 233,389 793,390 48391 ],392 [393 312,394 685,395 514,396 895397 ],398 [399 89,400 959,401 382,402 496403 ],404 [405 13,406 295,407 462,408 138409 ],410 [411 650,412 175,413 605,414 658415 ],416 [417 702,418 710,419 597,420 78421 ],422 [423 980,424 363,425 972,426 601427 ],428 [429 396,430 204,431 831,432 842433 ],434 [435 473,436 695,437 586,438 570439 ],440 [441 489,442 952,443 162,444 558445 ],446 [447 943,448 658,449 538,450 631451 ],452 [453 352,454 805,455 378,456 26457 ],458 [459 553,460 762,461 733,462 459463 ],464 [465 433,466 478,467 633,468 363469 ],470 [471 695,472 798,473 258,474 754475 ],476 [477 925,478 386,479 176,480 965481 ],482 [483 515,484 978,485 159,486 553487 ],488 [489 792,490 195,491 973,492 937493 ],494 [495 55,496 327,497 986,498 932499 ],500 [501 403,502 497,503 771,504 206505 ],506 [507 259,508 304,509 96,510 34511 ],512 [513 549,514 683,515 712,516 834517 ],518 [519 826,520 854,521 725,522 744523 ],524 [525 701,526 614,527 437,528 286529 ],530 [531 856,532 540,533 886,534 471535 ],536 [537 906,538 107,539 316,540 723541 ],542 [543 842,544 818,545 799,546 122547 ],548 [549 632,550 203,551 150,552 211553 ],554 [555 554,556 291,557 251,558 576559 ],560 [561 750,562 773,563 51,564 850565 ],566 [567 556,568 337,569 97,570 893571 ],572 [573 958,574 245,575 750,576 942577 ],578 [579 336,580 598,581 20,582 245583 ],584 [585 452,586 24,587 651,588 980589 ],590 [591 985,592 335,593 516,594 759595 ],596 [597 71,598 52,599 314,600 62601 ],602 [603 502,604 740,605 751,606 62607 ],608 [609 325,610 340,611 652,612 859613 ],614 [615 935,616 541,617 904,618 663619 ],620 [621 642,622 783,623 106,624 758625 ],626 [627 187,628 762,629 245,630 279631 ],632 [633 83,634 535,635 672,636 720637 ],638 [639 259,640 278,641 919,642 309643 ],644 [645 620,646 379,647 677,648 69649 ],650 [651 299,652 269,653 351,654 192655 ],656 [657 32,658 348,659 49,660 747661 ],662 [663 527,664 289,665 930,666 233667 ],668 [669 20,670 980,671 100,672 349673 ],674 [675 732,676 43,677 798,678 900679 ],680 [681 122,682 826,683 222,684 920685 ],686 [687 485,688 797,689 907,690 32691 ],692 [693 872,694 500,695 430,696 918697 ],698 [699 642,700 772,701 931,702 465703 ],704 [705 216,706 699,707 327,708 148709 ],710 [711 202,712 62,713 364,714 383715 ],716 [717 327,718 204,719 794,720 394721 ],722 [723 359,724 262,725 477,726 543727 ],728 [729 108,730 246,731 281,732 78733 ],734 [735 172,736 30,737 703,738 603739 ],740 [741 864,742 37,743 595,744 722745 ],746 [747 301,748 927,749 232,750 53751 ],752 [753 711,754 319,755 41,756 824757 ],758 [759 614,760 958,761 54,762 92763 ],764 [765 159,766 75,767 692,768 919769 ],770 [771 127,772 202,773 837,774 271775 ],776 [777 336,778 448,779 555,780 999781 ],782 [783 802,784 232,785 315,786 933787 ],788 [789 63,790 838,791 384,792 153793 ],794 [795 41,796 590,797 483,798 108799 ],800 [801 190,802 934,803 256,804 548805 ],806 [807 826,808 930,809 761,810 655811 ],812 [813 715,814 706,815 4,816 183817 ],818 [819 364,820 733,821 611,822 65823 ],824 [825 580,826 462,827 345,828 678829 ],830 [831 862,832 99,833 625,834 53835 ],836 [837 458,838 678,839 181,840 504841 ],842 [843 376,844 110,845 784,846 814847 ],848 [849 547,850 454,851 613,852 12853 ],854 [855 298,856 787,857 403,858 41859 ],860 [861 118,862 642,863 65,864 635865 ],866 [867 819,868 725,869 970,870 889871 ],872 [873 460,874 338,875 605,876 122877 ],878 [879 902,880 994,881 488,882 259883 ],884 [885 886,886 104,887 719,888 378889 ],890 [891 775,892 225,893 673,894 471895 ],896 [897 328,898 200,899 726,900 559901 ],902 [903 568,904 27,905 337,906 12907 ],908 [909 964,910 503,911 103,912 93913 ],914 [915 891,916 431,917 99,918 542919 ],920 [921 536,922 714,923 608,924 330925 ],926 [927 850,928 907,929 399,930 666931 ],932 [933 417,934 932,935 776,936 301937 ],938 [939 202,940 794,941 59,942 762943 ],944 [945 962,946 109,947 283,948 560949 ],950 [951 405,952 586,953 496,954 988955 ],956 [957 822,958 994,959 94,960 487961 ],962 [963 890,964 290,965 210,966 653967 ],968 [969 114,970 78,971 874,972 410973 ],974 [975 716,976 781,977 723,978 851979 ],980 [981 712,982 297,983 228,984 531985 ],986 [987 45,988 89,989 167,990 617991 ],992 [993 983,994 964,995 256,996 303997 ],998 [999 319,1000 901,1001 554,1002 3461003 ],1004 [1005 899,1006 330,1007 811,1008 7761009 ],1010 [1011 854,1012 59,1013 832,1014 5481015 ],1016 [1017 714,1018 294,1019 175,1020 6071021 ],1022 [1023 368,1024 755,1025 96,1026 6831027 ],1028 [1029 750,1030 924,1031 973,1032 2141033 ],1034 [1035 346,1036 456,1037 224,1038 811039 ],1040 [1041 15,1042 607,1043 596,1044 7981045 ],1046 [1047 845,1048 754,1049 577,1050 8081051 ],1052 [1053 638,1054 676,1055 379,1056 7941057 ],1058 [1059 263,1060 840,1061 236,1062 1901063 ],1064 [1065 674,1066 92,1067 888,1068 5601069 ],1070 [1071 378,1072 612,1073 86,1074 7551075 ],1076 [1077 743,1078 128,1079 651,1080 6891081 ],1082 [1083 644,1084 379,1085 951,1086 1531087 ],1088 [1089 666,1090 339,1091 810,1092 5251093 ],1094 [1095 828,1096 11,1097 238,1098 951099 ],1100 [1101 933,1102 123,1103 758,1104 1951105 ],1106 [1107 308,1108 899,1109 420,1110 9811111 ],1112 [1113 522,1114 305,1115 748,1116 8141117 ],1118 [1119 38,1120 20,1121 871,1122 3311123 ],1124 [1125 762,1126 89,1127 56,1128 8391129 ],1130 [1131 206,1132 283,1133 662,1134 6421135 ],1136 [1137 96,1138 828,1139 896,1140 7831141 ],1142 [1143 29,1144 85,1145 636,1146 2971147 ],1148 [1149 583,1150 717,1151 56,1152 2311153 ],1154 [1155 587,1156 222,1157 613,1158 4641159 ],1160 [1161 477,1162 327,1163 845,1164 8631165 ],1166 [1167 13,1168 564,1169 425,1170 5361171 ],1172 [1173 878,1174 575,1175 686,1176 2791177 ],1178 [1179 411,1180 535,1181 154,1182 7011183 ],1184 [1185 418,1186 477,1187 286,1188 3851189 ],1190 [1191 714,1192 124,1193 366,1194 5661195 ],1196 [1197 571,1198 440,1199 744,1200 771