Maximum Coins in K Consecutive Lockers
Instructions
A hallway has an infinite row of lockers numbered 1, 2, 3, ....
You are given an integer k and a 2D integer array ranges, where ranges[i] = [start, end, coins] means every locker with a number in [start, end] contains exactly coins coins. No two ranges overlap, and any locker not covered by a range contains 0 coins. The ranges are not guaranteed to be sorted.
Choose k consecutive lockers so that the total number of coins inside them is maximized.
Return that maximum total modulo 10^9 + 7.
Example 1:
Input: k = 4, ranges = [[2,3,4],[5,5,9],[8,9,3]]
Output: 17
Explanation: The lockers hold
locker: 1 2 3 4 5 6 7 8 9 10 ...
coins: 0 4 4 0 9 0 0 3 3 0 ...
Checking every window of size 4:
[1..4] -> 0 + 4 + 4 + 0 = 8
[2..5] -> 4 + 4 + 0 + 9 = 17
[3..6] -> 4 + 0 + 9 + 0 = 13
[4..7] -> 0 + 9 + 0 + 0 = 9
[5..8] -> 9 + 0 + 0 + 3 = 12
[6..9] -> 0 + 0 + 3 + 3 = 6
Lockers 2 through 5 give the largest total, so the answer is 17.
Example 2:
Input: k = 5, ranges = [[9,10,1],[1,4,2],[7,7,7],[6,6,5]]
Output: 16
Explanation: After sorting, the lockers hold 2 2 2 2 0 5 7 0 1 1 for lockers 1 through 10. The window [3..7] collects 2 + 2 + 0 + 5 + 7 = 16, which is the best of all windows.
Example 3:
Input: k = 3, ranges = [[1,5,1],[7,7,10]]
Output: 11
Explanation: The best window is [5..7], collecting 1 + 0 + 10 = 11. Note that it does not start at the beginning of any range; it ends at the end of one. Only checking windows that start at a range's first locker would give 10, which is wrong.
Example 4:
Input: k = 1000000000, ranges = [[1,1000000000,1000000]]
Output: 993000007
Explanation: All 10^9 lockers are taken, holding 10^15 coins in total. 10^15 mod (10^9 + 7) = 993000007.
Constraints:
1 <= ranges.length <= 2 * 10^51 <= k <= 10^91 <= ranges[i][0] <= ranges[i][1] <= 10^91 <= ranges[i][2] <= 10^6- No two ranges overlap.
Function Signature
Online Judge
Result will appear here after submission.