diff options
-rw-r--r-- | max_fruits_harvested_k_step.c | 136 | ||||
-rw-r--r-- | max_fruits_harvested_k_step.py | 72 |
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)) |