Most-Visited Position Across Sprints
Problem statement
A runner trains by sprinting between markers placed at integer positions 1..n. The runner follows a list of markers in order; each consecutive pair defines one sprint, a straight run between those two markers (for example, from position 4 to position 1). Every integer position on that closed interval, endpoints included, is visited once by that sprint, regardless of direction.
Given n and the ordered list of markers sprints, compute how many times each position 1..n is visited in total, and return the maximum visit count over all positions.
Complete:
def getMostVisited(n: int, sprints: list[int]) -> int:
Constraints:
- $1 \le n \le 10^9$ (treat the position range as large -- you cannot afford to touch every position of every interval).
- $2 \le \text{len(sprints)} \le 10^5$, each marker in
1..n.
Examples:
sprints = [1, 3, 5, 3],n = 5-> intervals[1,3],[3,5],[3,5]give per-position totals1, 1, 3, 2, 2; the answer is3(position 3).sprints = [2, 4, 1, 3],n = 5-> intervals[2,4],[1,4],[1,3]give per-position totals2, 3, 3, 2, 0; the answer is3(positions 2 and 3).
Show hint
Is there a way to record a whole range of +1 updates without touching every position inside it?
Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.