Maximum Coupon Credit and Its Time Windows
Problem statement
Each coupon gives a fixed amount of credit during a time interval in one day. All coupons valid at the same moment can be used together. Find the largest total credit available at once and every time range where that total is available.
For this exercise, times are whole minutes after midnight. A coupon [start, end, credit] is valid from start, inclusive, to end, exclusive. Its credit is added to every other valid coupon.
Return a matrix whose first row is [maximumCredit]. The remaining rows are the maximal nonempty ranges [start, end] attaining that value, sorted by start time. Join adjacent ranges when their total credit stays equal to the maximum, even if the set of valid coupons changes. If there are no coupons, return [[0]].
Function
maximumCouponCredit(coupons: int[][]) → long[][]Examples
Example 1
coupons = [[600,660,5],[780,900,10]]return = [[10],[780,900]]The reported 10:00–11:00 coupon is worth 5 and the 13:00–15:00 coupon is worth 10. They do not overlap, so the maximum is 10 from minute 780 to 900.
Example 2
coupons = [[0,4,5],[2,6,7],[6,8,12]]return = [[12],[2,4],[6,8]]From 2 to 4, credits 5 and 7 add to 12. From 6 to 8, the third coupon alone gives 12. Between 4 and 6, only credit 7 is available, so the maximum ranges stay separate.
Example 3
coupons = [[0,2,5],[2,4,5]]return = [[5],[0,4]]The total remains 5 across time 2. The two adjacent maximum ranges join into [0,4], although different coupons are active.
Constraints
- 0 <= coupons.length <= 20000
- Each coupon has exactly 3 integers.
- 0 <= coupons[i][0] <= 1439
- 1 <= coupons[i][1] <= 1440
- 1 <= coupons[i][2] <= 1000000
- Every coupon satisfies start < end.
- 0 <= coupons[i][j] <= 1000000