Smallest Integer Point Lit by the Most Street Lamps on a Line

Street lamps stand along a straight road, which is modeled as the number line. Each lamp has a position c and a radius r, and it lights every point x with c - r <= x <= c + r. Find the integer point that is lit by the largest number of lamps. If several integer points are lit by that same largest number of lamps, return the smallest of them.

Function Signature

def most_lit_point(lamps: list[list[int]]) -> int:

Each lamp is given as [c, r].

Rules

• Both ends of a lamp's range are lit: the points c - r and c + r count.
• Ranges may overlap, nest, coincide or touch, and several lamps may share a position.
• A lamp with radius 0 lights only the point c.
• Only integer points are candidates. The answer is the smallest integer point whose lamp count equals the maximum lamp count over all integer points.

Constraints

• 1 <= len(lamps) <= 10^5
• -10^9 <= c <= 10^9
• 0 <= r <= 10^9
• Every range end c - r and c + r lies between -2 * 10^9 and 2 * 10^9, which fits in a 32-bit signed integer (whose limit is 2^31 - 1 = 2147483647).

Examples

Example 1

Input: lamps = [[-2, 3], [1, 2], [5, 1]]
Output: -1

The lamps light [-5, 1], [-1, 3] and [4, 6]. Every point from -1 through 1 is lit by two lamps, and no point is lit by three, so the smallest point lit by two lamps is -1.

Example 2

Input: lamps = [[0, 1], [2, 1], [6, 2], [7, 1]]
Output: 1

The ranges are [-1, 1], [1, 3], [4, 8] and [6, 8]. Point 1 is the shared end of the first two ranges, so two lamps light it. Points 6, 7 and 8 are also lit by two lamps. No point is lit by three, and 1 is the smallest of the tied points.

Example 3

Input: lamps = [[10, 0], [3, 2], [20, 5]]
Output: 1

The ranges [10, 10], [1, 5] and [15, 25] do not overlap, so the maximum is one lamp, and the smallest lit point is 1.