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.

Smallest Integer Point Lit by the Most Street Lamps

Hints

1. The lit coordinates can span about 4 * 10^9 integer points, far too many to check one at a time. Think about where the number of lamps lighting a point can actually change as you move along the road.
2. Both ends of a range are lit: a point where one range ends and another begins is lit by both lamps, while a range that ends at p does not light p + 1.
3. Ties go to the smallest point. Think about which points can be the leftmost point of a run that reaches the maximum count.

Approach

Sweep over range events. Each lamp contributes a start event at c - r (count +1) and an end event at c + r + 1 (count -1). Placing the end event one past c + r keeps the inclusive right end lit, so ranges that touch at a shared end both count there, while ranges with c1 + r1 + 1 == c2 - r2 never overlap. Sort the start coordinates and the end coordinates separately, then merge them in increasing order, applying every event at one coordinate before reading the count.

Invariant: after all events at coordinates <= x have been applied, count equals the number of lamps that light x, and it stays constant up to the next event coordinate. The smallest point with the maximum count is therefore an event coordinate where the count rose, which is always some range start c - r. Scanning coordinates in increasing order and replacing the best only on a strictly greater count returns the smallest tied point. After the last start, the count can only fall, so the scan stops there.

Edge cases: a single lamp returns c - r; a radius-0 lamp has start c and end event c + 1; coincident lamps stack at the same coordinates; an answer always exists because n >= 1. Every coordinate stays within [-2 * 10^9, 2 * 10^9 + 1], inside the 32-bit signed range, and the Java and C++ references use 64-bit intermediates anyway.

• Time complexity: O(n log n)
• Space complexity: O(n)