Find leftmost point of maximum brightness
Overview
This question evaluates understanding of interval overlap counting, efficient use of ordered data structures for range events, tie-breaking logic, and robustness to numeric edge cases such as large coordinates and floating-point radii.
You are given an array of lights, where each light is [p, r] representing a lamp centered at coordinate p on the real number line with radius r, illuminating the closed interval [p − r, p + r]. The brightness at point x is the count of intervals that contain x. Return the smallest coordinate x with maximum brightness. If the maximum brightness occurs over an interval, return its left endpoint. Design an algorithm that runs in O(n log n) time without enumerating individual points on the number line, and explain your approach (e.g., event sweep or ordered map), tie-breaking, and correctness. Discuss how you would handle large coordinates (up to 1e 9), negative positions, and floating-point radii.