aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_fruits_harvested_k_step.c26
-rw-r--r--max_fruits_harvested_k_step.py54
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__":