Description
There are some prizes on the X-axis. You are given an integer array prizePositions that is sorted in non-decreasing order, and an integer k. Select two segments of length k. Return the maximum number of prizes you can win.
Examples
prizePositions = [1,1,2,2,3,3,5], k = 27Select [1,3] and [3,5] for all prizes.
prizePositions = [1,4,7,10,13,16], k = 56With k=5, each segment covers positions within 5 units. First segment [1,6] covers prizes at positions 1 and 4 (2 prizes). Second segment [12,17] covers prizes at positions 13 and 16 (2 prizes). However, it is possible to do better: segment [1,6] gets positions 1,4 (2 prizes) and segment [7,12] gets positions 7,10 (2 prizes). Best solution: [1,6] covers 1,4 and [10,15] covers 10,13, or optimally [4,9] covers 4,7 and [13,18] covers 13,16, giving us all 6 prizes total.
prizePositions = [5,5,5,5,20,21,22], k = 37First segment [5,8] covers all four prizes at position 5. Second segment [20,23] covers all three prizes at positions 20, 21, and 22. Since the segments don't overlap (position 8 < position 20), it is possible to collect all 7 prizes total.
Constraints
- •
1 ≤ prizePositions.length ≤ 10^5 - •
1 ≤ prizePositions[i] ≤ 10^9