Early bird rank
MediumOnline Assessment
Count the overtakes in a staggered-start trail run and find the runner who made the most.
Runners are released one at a time, numbered 0, 1, 2, ... in release order. Runner k starts at minute k * gap and takes duration[k] minutes to finish, so runner k finishes at minute k * gap + duration[k].
The durations come from the club squads. A squad [count, first, step] supplies count consecutive runners; the first has duration first, and each next runner in the squad has the previous runner's duration plus step (step may be negative or zero). Squads are released in the order given, one after the other, and the numbering runs on across squads.
Runner j overtakes runner i when i started strictly earlier than j and j finishes strictly earlier than i. Finishing at the same minute is not an overtake.
Input: gap, the number of minutes between consecutive releases, and squads, a list of [count, first, step] triples.
Output: a list [total, runner, made]: the total number of overtakes over all pairs of runners, the number of the runner who overtook the most other runners (the smallest number if several tie), and how many runners that runner overtook. If nobody overtakes anybody, return [0, 0, 0]. If there are no runners at all, return [0, -1, 0].
There can be tens of thousands of runners, so comparing every pair of runners will be too slow.
Example 1
- Input:
- [10,[[3,100,-30]]]
- Output:
- [3,2,2]
- Explanation
- One squad of three runners with durations 100, 70 and 40 minutes, released every 10 minutes. They finish at minutes 100, 80 and 60. Runner 1 passes runner 0, and runner 2 passes runners 0 and 1, so there are 3 overtakes in total and runner 2 made the most (2): [3, 2, 2].
Example 2
- Input:
- [10,[[2,50,-30],[2,50,-30]]]
- Output:
- [2,1,1]
- Explanation
- Durations are 50, 20, 50, 20, so the finish minutes are 50, 30, 70 and 50. Runner 1 passes runner 0, and runner 3 passes runner 2. Runner 3 finishes at minute 50, the same as runner 0, which is not a pass. Two overtakes, and runners 1 and 3 both made one, so the earlier runner wins the tie: [2, 1, 1].
Example 3
- Input:
- [0,[[4,50,-10]]]
- Output:
- [0,0,0]
- Explanation
- With a gap of 0 everyone starts together, so nobody started earlier than anybody else and nothing counts as an overtake, however different the paces are. No runner passed anyone, so the best runner is runner 0 by the tie rule: [0, 0, 0].
Constraints
0 <= gap <= 1,0000 <= squads.length <= 40- each squad is
[count, first, step]with1 <= count,-1,000 <= step <= 1,000, and every duration it produces between1and1,000,000 - the squads together hold at most
30,000runners