Problem library

Zone Boosts

Medium
difference arrayprefix sums
Warm up with this problem Battle on it

A race track is split into n zones numbered 0 to n - 1, all starting at speed bonus 0. Each entry of boosts is [from, to, amount]: every zone from from through to (inclusive) gets amount added to its bonus. Amounts can be negative.

After all boosts, return [bestBonus, firstZone]: the highest bonus on the track and the lowest-numbered zone that has it. The largest test has 100,000 zones and 15,000 boosts.

Examples

Input: n = 5, boosts = [[0,2,3],[1,4,2],[2,2,-10]]
Output: [5,1]
Input: n = 3, boosts = []
Output: [0,0]