diff options
Diffstat (limited to 'max_fruits_harvested_k_step.c')
-rw-r--r-- | max_fruits_harvested_k_step.c | 136 |
1 files changed, 136 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 +} |