aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_fruits_harvested_k_step.c136
-rw-r--r--max_fruits_harvested_k_step.py72
2 files changed, 208 insertions, 0 deletions
diff --git a/max_fruits_harvested_k_step.c b/max_fruits_harvested_k_step.c
new file mode 100644
index 0000000..c5a2778
--- /dev/null
+++ b/max_fruits_harvested_k_step.c
@@ -0,0 +1,136 @@
+// 2106. Maximum Fruits Harvested After at Most K Steps
+#include "leetcode.h"
+
+/*
+ * fruits are available at some positions on an infinite x-axis. you are given a
+ * 2d integer array 'fruits' where 'fruits[i] = [positions[i], amount[i]]'
+ * depicts 'amount[i]' fruits at the position 'position[i]'. 'fruits' is already
+ * sorted by 'position[i]' in ascending order, and eash 'position[i]' is unique.
+ * you are also given an integer 'startPos' and an integer 'k'. initially, y-u
+ * are at the position 'startPos'. from any position, you can either walk to the
+ * left or right. it takes one step to move one unit on the x-axis, and you can
+ * walk at most 'k' steps in total. for every position you reach, you harvest
+ * all the fruits at that position, and the fruits will dsiappear from that
+ * position.
+ */
+
+void bfs(int **fruits, int fruitsSize, int start, int *left, int *right) {
+ *left = 0;
+ *right = fruitsSize - 1;
+ while (*left <= *right) {
+ int mid = (*left + *right) / 2;
+ if (fruits[mid][0] < start)
+ *left = mid + 1;
+ else if (fruits[mid][0] > start)
+ *right = mid - 1;
+ else {
+ *left = mid;
+ *right = mid;
+ break;
+ }
+ }
+}
+
+int find_max_right(int **fruits, int fruitsSize, int curr, int k) {
+ int startPos = curr, max_left = curr - 1, sum_left = 0, max = 0,
+ sum_right = 0;
+ for (; max_left >= 0; max_left--) {
+ if ((fruits[curr][0] - fruits[max_left][0]) < k)
+ sum_left += fruits[max_left][1];
+ else {
+ max_left++;
+ break;
+ }
+ }
+ if (max_left == -1)
+ max_left++;
+ while (1) {
+ sum_right += fruits[curr][1];
+ if (sum_right + sum_left > max)
+ max = sum_right + sum_left;
+ if (curr == fruitsSize - 1)
+ break;
+ else {
+ curr++;
+ k -= fruits[curr][0] - fruits[curr - 1][0];
+ if (k < 0)
+ break;
+ else if (k > fruits[curr][0] - fruits[startPos][0]) {
+ while (max_left < startPos &&
+ fruits[curr][0] - fruits[max_left][0] > k) {
+ sum_left -= fruits[max_left][1];
+ max_left++;
+ }
+ } else
+ sum_left = 0;
+ }
+ }
+ return max;
+}
+
+int find_max_left(int **fruits, int fruitsSize, int curr, int k) {
+ int startPos = curr, max_right = curr + 1, sum_right = 0, max = 0,
+ sum_left = 0;
+ for (; max_right < fruitsSize; max_right++) {
+ if (fruits[max_right][0] - fruits[curr][0] <= k)
+ sum_right += fruits[max_right][1];
+ else {
+ max_right--;
+ break;
+ }
+ }
+ if (max_right == fruitsSize)
+ max_right--;
+ while (1) {
+ sum_left += fruits[curr][1];
+ if (sum_right + sum_left > max)
+ max = sum_right + sum_left;
+ if (!curr)
+ break;
+ else {
+ curr--;
+ k -= fruits[curr + 1][0] - fruits[curr][0];
+ if (k < 0)
+ break;
+ else if (k > fruits[startPos][0] - fruits[curr][0]) {
+ while (max_right > startPos &&
+ fruits[max_right][0] - fruits[curr][0] > k) {
+ sum_right -= fruits[max_right][1];
+ max_right--;
+ }
+ } else
+ sum_right = 0;
+ }
+ }
+ return max;
+}
+
+int maxTotalFruits(int **fruits, int fruitsSize, int *fruitsColSize,
+ int startPos, int k) {
+ int left = -1, right = -1;
+ bfs(fruits, fruitsSize, startPos, &right, &left);
+ if (right < fruitsSize) {
+ int new_k = k - (fruits[right][0] - startPos);
+ right = new_k >= 0 ? find_max_right(fruits, fruitsSize, right, new_k) : 0;
+ } else
+ right = 0;
+ if (left > -1) {
+ int new_k = k - (startPos - fruits[left][0]);
+ left = new_k >= 0 ? find_max_left(fruits, fruitsSize, left, new_k) : 0;
+ } else
+ left = 0;
+ return left > right ? left : right;
+}
+
+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
+}
diff --git a/max_fruits_harvested_k_step.py b/max_fruits_harvested_k_step.py
new file mode 100644
index 0000000..bc5b1b0
--- /dev/null
+++ b/max_fruits_harvested_k_step.py
@@ -0,0 +1,72 @@
+# 2106. Maximum Fruits Harvested After at Most K Steps
+import bisect
+
+"""
+fruits are available at some positions on an infinite x-axis. you are given a
+2d integer array 'fruits' where 'fruits[i] = [positions[i], amount[i]]'
+depicts 'amount[i]' fruits at the position 'position[i]'. 'fruits' is already
+sorted by 'position[i]' in ascending order, and eash 'position[i]' is unique.
+you are also given an integer 'startPos' and an integer 'k'. initially, y-u
+are at the position 'startPos'. from any position, you can either walk to the
+left or right. it takes one step to move one unit on the x-axis, and you can
+walk at most 'k' steps in total. for every position you reach, you harvest
+all the fruits at that position, and the fruits will dsiappear from that
+position.
+"""
+
+
+class Solution(object):
+ def maxTotalFruits(self, fruits, startPos, k):
+ """
+ :type fruits: List[List[int]]
+ :type startPos: int
+ :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)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxTotalFruits(fruits=[[2, 8], [6, 3], [8, 6]], startPos=5, k=4))
+ print(
+ obj.maxTotalFruits(
+ fruits=[[0, 9], [4, 1], [5, 7], [6, 2], [7, 4], [10, 9]], startPos=5, k=4
+ )
+ )
+ print(obj.maxTotalFruits(fruits=[[0, 3], [6, 4], [8, 5]], startPos=3, k=2))