Split mat audit
MediumOnline Assessment
Audit marathon timing-mat reads and flag the readings that no runner could have run.
Timing mats lie along the course at the distances in mats (metres from the start line, in increasing order; mat i is the one at mats[i]). Each read is [bib, matIndex, seconds]: runner bib crossed mat matIndex seconds after the starting gun. The start line itself counts as a "good read" at 0 m and 0 s for everyone. Reads arrive in any order, and a runner may miss mats.
Check each runner separately, going through their reads in increasing matIndex order:
- If a runner has several reads at the same mat (tag bounce), only the one with the smallest
secondsis kept. - Compare each kept read with the runner's last good read (initially the start line). It is impossible if the time since that good read is faster than 150 seconds per kilometre over the distance between the two points; that is, if
elapsedSeconds * 1000 < distanceMetres * 150. Exactly 150 s/km is allowed. Zero or negative elapsed time over a positive distance is also impossible. - A good read becomes the new last good read. An impossible read is flagged and dropped: it is never used as a reference for later reads.
Input: mats, a list of distances; reads, a list of [bib, matIndex, seconds].
Output: a list [bib, flaggedMatIndexes] for every runner with at least one flagged read, sorted by bib ascending, where flaggedMatIndexes is the list of flagged mat indexes in ascending order. Return [] if nothing was flagged.
Example 1
- Input:
- [[5000,10000,21097],[[31,0,700],[12,0,1500],[31,1,2900],[12,1,3000],[31,0,1400],[12,2,6500],[31,2,6000]]]
- Output:
- [[31,[0]]]
- Explanation
- A 5,000 m mat needs at least 750 s. Bib 31 first read mat 0 at 700 s (the later duplicate at 1,400 s is discarded), which is too fast, so mat 0 is flagged. Its reads at mats 1 and 2 are checked against the gun (0 m, 0 s): 10,000 m in 2,900 s is fine, and 11,097 m more in 3,100 s is fine. Bib 12 is clean.
Example 2
- Input:
- [[5000,10000,15000],[[5,0,1000],[6,2,2000],[5,1,1100],[5,2,2600]]]
- Output:
- [[5,[1]],[6,[2]]]
- Explanation
- Bib 5's read at mat 1 is 100 s after mat 0 for 5,000 m: flagged and dropped. The read at mat 2 is compared with mat 0 instead (10,000 m in 1,600 s, needing 1,500 s), so it is fine. Bib 6 only has a mat 2 read, 15,000 m in 2,000 s from the gun, needing 2,250 s: flagged.
Example 3
- Input:
- [[1000,2000],[[9,0,150],[9,1,300],[4,0,200],[4,1,200]]]
- Output:
- [[4,[1]]]
- Explanation
- Bib 9 runs 1,000 m in exactly 150 s, the limit, which is allowed. Bib 4 appears at mat 1 at the same second as mat 0, so the segment took 0 s and is flagged.
Constraints
1 <= mats.length <= 8;matsis strictly increasing, values are metres from the start line, up to42,1950 <= reads.length <= 1,500; each read is[bib, matIndex, seconds]with0 <= matIndex < mats.lengthand0 <= seconds <= 86,400bibis an integer from1to99,999; reads arrive in any order