2106. Maximum Fruits Harvested After at Most K Steps Hard

1/**
2 * [2106] Maximum Fruits Harvested After at Most K Steps
3 *
4 * Fruits are available at some positions on an infinite x-axis. You are given a 2D integer array fruits where fruits[i] = [positioni, amounti] depicts amounti fruits at the position positioni. fruits is already sorted by positioni in ascending order, and each positioni is unique.
5 * You are also given an integer startPos and an integer k. Initially, you 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 disappear from that position.
6 * Return the maximum total number of fruits you can harvest.
7 *  
8 * Example 1:
9 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/1.png" style="width: 472px; height: 115px;" />
10 * Input: fruits = [[2,8],[6,3],[8,6]], startPos = 5, k = 4
11 * Output: 9
12 * Explanation: 
13 * The optimal way is to:
14 * - Move right to position 6 and harvest 3 fruits
15 * - Move right to position 8 and harvest 6 fruits
16 * You moved 3 steps and harvested 3 + 6 = 9 fruits in total.
17 * 
18 * Example 2:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/2.png" style="width: 512px; height: 129px;" />
20 * Input: fruits = [[0,9],[4,1],[5,7],[6,2],[7,4],[10,9]], startPos = 5, k = 4
21 * Output: 14
22 * Explanation: 
23 * You can move at most k = 4 steps, so you cannot reach position 0 nor 10.
24 * The optimal way is to:
25 * - Harvest the 7 fruits at the starting position 5
26 * - Move left to position 4 and harvest 1 fruit
27 * - Move right to position 6 and harvest 2 fruits
28 * - Move right to position 7 and harvest 4 fruits
29 * You moved 1 + 3 = 4 steps and harvested 7 + 1 + 2 + 4 = 14 fruits in total.
30 * 
31 * Example 3:
32 * <img alt="" src="https://assets.leetcode.com/uploads/2021/11/21/3.png" style="width: 476px; height: 100px;" />
33 * Input: fruits = [[0,3],[6,4],[8,5]], startPos = 3, k = 2
34 * Output: 0
35 * Explanation:
36 * You can move at most k = 2 steps and cannot reach any position with fruits.
37 * 
38 *  
39 * Constraints:
40 * 
41 * 	1 <= fruits.length <= 10^5
42 * 	fruits[i].length == 2
43 * 	0 <= startPos, positioni <= 2 * 10^5
44 * 	positioni-1 < positioni for any i > 0 (0-indexed)
45 * 	1 <= amounti <= 10^4
46 * 	0 <= k <= 2 * 10^5
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/
52// discuss: https://leetcode.com/problems/maximum-fruits-harvested-after-at-most-k-steps/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn max_total_fruits(fruits: Vec<Vec<i32>>, start_pos: i32, k: i32) -> i32 {
58        0
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_2106() {
70    }
71}
72