Smallest Integer Point Lit by the Most Street Lamps on a Line
Company: Hudson
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
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
```python
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**
```text
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**
```text
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**
```text
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.
Overview: Online assessment coding problem: street lamps on a number line each light a closed interval around their position, and you must return the integer point lit by the most lamps, choosing the smallest such point on ties. It tests interval overlap counting over very large coordinate ranges.
Read the full Hudson Software Engineer interview experience this question came from
Street lamps stand along a straight road, which is modeled as the number line. Each lamp is given as a pair `[c, r]`: it stands at position `c`, has radius `r`, and lights every point `x` with `c - r <= x <= c + r`.
Return 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.
### 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. Every lamp lights at least its own point `c`, so an answer always exists.
### 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`). No input value or answer exceeds `2^31 - 1` in absolute value, so Java and C++ return an `int`.
### Examples
**Example 1**
```text
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**
```text
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.
Constraints
- 1 <= len(lamps) <= 10^5
- Each lamp is a pair [c, r]
- -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 (limit 2^31 - 1 = 2147483647)
Examples
Input: ([[-2, 3], [1, 2], [5, 1]],)
Expected Output: -1
Explanation: Source example 1: ranges [-5, 1], [-1, 3] and [4, 6]; points -1 through 1 are lit by two lamps and none by three, so the smallest is -1.
Input: ([[0, 1], [2, 1], [6, 2], [7, 1]],)
Expected Output: 1
Explanation: Source example 2: [-1, 1] and [1, 3] touch at 1, which counts both lamps; points 6 through 8 also have two, and 1 is the smallest tied point.
Hints
- 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.
- 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.
- Ties go to the smallest point. Think about which points can be the leftmost point of a run that reaches the maximum count.