diff options
author | Jack Sangdahl <[email protected]> | 2025-08-03 11:22:39 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-03 11:22:39 +0100 |
commit | 23f4ec5bfd6efc70417e3952217e11efd75b9d23 (patch) | |
tree | f31f5f9980a940b6c297177fe3e2043763f70ddd | |
parent | 0025b8254ac7fd37f1c82686f3cb728e1ef2e1fe (diff) | |
download | leetcode-23f4ec5bfd6efc70417e3952217e11efd75b9d23.tar.gz leetcode-23f4ec5bfd6efc70417e3952217e11efd75b9d23.zip |
2106. maximum fruits harvested after at most k steps
-rw-r--r-- | max_fruits_harvested_k_step.c | 26 | ||||
-rw-r--r-- | max_fruits_harvested_k_step.py | 54 |
2 files changed, 33 insertions, 47 deletions
diff --git a/max_fruits_harvested_k_step.c b/max_fruits_harvested_k_step.c index c5a2778..47776de 100644 --- a/max_fruits_harvested_k_step.c +++ b/max_fruits_harvested_k_step.c @@ -123,14 +123,20 @@ int maxTotalFruits(int **fruits, int fruitsSize, int *fruitsColSize, } int main() { - int f1[3][2] = {{2, 8}, {6, 3}, {8, 6}}, - f2[6][2] = {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}}, - f3[3][2] = {{0, 3}, {6, 4}, {8, 5}}; - int fcs1 = ARRAY_SIZE(f1), fcs2 = ARRAY_SIZE(f2), fcs3 = ARRAY_SIZE(f3); - printf("%d\n", maxTotalFruits((int **)f1, ARRAY_SIZE(f1[0]), &fcs1, 5, - 4)); // expect: 9 - printf("%d\n", maxTotalFruits((int **)f2, ARRAY_SIZE(f2[0]), &fcs2, 5, - 4)); // expect: 14 - printf("%d\n", maxTotalFruits((int **)f3, ARRAY_SIZE(f3[0]), &fcs3, 3, - 2)); // expect: 0 + int f1i[3][2] = {{2, 8}, {6, 3}, {8, 6}}, + f2i[6][2] = {{0, 9}, {4, 1}, {5, 7}, {6, 2}, {7, 4}, {10, 9}}, + f3i[3][2] = {{0, 3}, {6, 4}, {8, 5}}; + struct two_d_arr f1, f2, f3; + two_d_arr_init(&f1, ARRAY_SIZE(f1i), ARRAY_SIZE(f1i[0]), f1i); + two_d_arr_init(&f2, ARRAY_SIZE(f2i), ARRAY_SIZE(f2i[0]), f2i); + two_d_arr_init(&f3, ARRAY_SIZE(f3i), ARRAY_SIZE(f3i[0]), f3i); + printf("%d\n", + maxTotalFruits(f1.arr, f1.row_size, f1.col_size, 5, 4)); // expect: 9 + printf("%d\n", + maxTotalFruits(f2.arr, f2.row_size, f2.col_size, 5, 4)); // expect: 14 + printf("%d\n", + maxTotalFruits(f3.arr, f3.row_size, f3.col_size, 3, 2)); // expect: 0 + two_d_arr_free(&f1); + two_d_arr_free(&f2); + two_d_arr_free(&f3); } diff --git a/max_fruits_harvested_k_step.py b/max_fruits_harvested_k_step.py index bc5b1b0..fcbc7c4 100644 --- a/max_fruits_harvested_k_step.py +++ b/max_fruits_harvested_k_step.py @@ -1,5 +1,5 @@ # 2106. Maximum Fruits Harvested After at Most K Steps -import bisect +from bisect import bisect_left """ fruits are available at some positions on an infinite x-axis. you are given a @@ -23,42 +23,22 @@ class Solution(object): :type k: int :rtype: int """ - amt = {} - for a, b in fruits: - amt[a] = b - pos = [a for a, b in fruits if a != startPos] - left, right, n = [], [], len(pos) - idx = bisect.insort_right(pos, startPos) - curr_f = 0 - for i in range(idx, n): - curr_pos = pos[i] - curr_f += amt[curr_pos] - right.append([curr_pos - pos, curr_f]) - curr_f = 0 - for i in range(idx - 1, -1, -1): - curr_pos = pos[i] - curr_f += amt[curr_pos] - left.append([pos - curr_pos, curr_f]) - ans = 0 - for r_dist, r_f in right: - if r_dist <= k: - curr_f = r_f - l_dist = k - 2 * r_dist - if l_dist > 0: - idx = bisect.bisect_right(left, [l_dist, float("inf")]) - if idx > 0: - curr_f += left[idx - 1][1] - ans = max(ans, curr_f) - for l_dist, l_f in left: - if l_dist <= k: - curr_f = l_f - r_dist = k - 2 * l_dist - if r_dist > 0: - idx = bisect.bisect_right(right, [r_dist, float("inf")]) - if idx > 0: - curr_f += right[idx - 1][1] - ans = max(ans, curr_f) - return ans + amt.get(pos, 0) + l = bisect_left([i[0] for i in fruits], startPos + k) + amount, total, r = 0, 0, l + while r < len(fruits) and fruits[r][0] <= startPos + k: + amount += fruits[r][1] + while ( + min( + startPos - 2 * fruits[l][0] + fruits[r][0], + 2 * fruits[r][0] - startPos - fruits[l][0], + ) + > k + ): + amount -= fruits[l][1] + l += 1 + total = max(total, amount) + r += 1 + return total if __name__ == "__main__": |