2555. Maximize Win From Two Segments
Description
There are some prizes on the X-axis. You are given an integer array prizePositions
that is sorted in non-decreasing order, where prizePositions[i]
is the position of the ith
prize. There could be different prizes at the same position on the line. You are also given an integer k
.
You are allowed to select two segments with integer endpoints. The length of each segment must be k
. You will collect all prizes whose position falls within at least one of the two selected segments (including the endpoints of the segments). The two selected segments may intersect.
- For example if
k = 2
, you can choose segments[1, 3]
and[2, 4]
, and you will win any prize i that satisfies1 <= prizePositions[i] <= 3
or2 <= prizePositions[i] <= 4
.
Return the maximum number of prizes you can win if you choose the two segments optimally.
Example 1:
Input: prizePositions = [1,1,2,2,3,3,5], k = 2 Output: 7 Explanation: In this example, you can win all 7 prizes by selecting two segments [1, 3] and [3, 5].
Example 2:
Input: prizePositions = [1,2,3,4], k = 0 Output: 2 Explanation: For this example, one choice for the segments is [3, 3] and [4, 4], and you will be able to get 2 prizes.
Constraints:
1 <= prizePositions.length <= 105
1 <= prizePositions[i] <= 109
0 <= k <= 109
prizePositions
is sorted in non-decreasing order.
Solutions
Solution 1: Dynamic Programming + Binary Search
We define $f[i]$ as the maximum number of prizes that can be obtained by selecting a segment of length $k$ from the first $i$ prizes. Initially, $f[0] = 0$. We define the answer variable as $ans = 0$.
Next, we enumerate the position $x$ of each prize, and use binary search to find the leftmost prize index $j$ such that $prizePositions[j] \geq x - k$. At this point, we update the answer $ans = \max(ans, f[j] + i - j)$, and update $f[i] = \max(f[i - 1], i - j)$.
Finally, we return $ans$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the number of prizes.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 |
|