Find the smallest possible maximum waiting time by choosing when to start moving through synchronized traffic lights.
Problem
You are given a one-dimensional route with synchronized traffic lights. At each light, you may have to wait before continuing, and your goal is to choose a starting moment so that the maximum waiting time at any light along the route is as small as possible.
Given the travel/waiting behavior of the lights as a sequence of values, determine the minimum feasible value of this worst-case waiting time.
This is an optimization problem: instead of directly constructing the best schedule, determine whether a candidate maximum waiting time is achievable, then search for the smallest achievable value.
What you need to compute
- Decide the minimum possible value of the largest waiting time encountered.
- If multiple starting moments achieve the same optimum, any of them is acceptable conceptually; only the minimum value is required.
Notes
- The exact interpretation is that each traffic light is synchronized and contributes a waiting requirement that depends on the chosen start time.
- A candidate answer is valid if every light can be handled without exceeding that maximum waiting time.
Input Format
- A sequence of integers describing the waiting requirements or timing offsets for the synchronized traffic lights.
- Additional problem-specific parameters, if any, are embedded in the route description.
- The task is to return the minimum possible value of the maximum waiting time.
Output Format
- Return a single integer: the smallest feasible maximum waiting time.
Constraints
- The route description is finite and can be processed in linear or near-linear time per feasibility check.
- Candidate answers fit in standard 32-bit signed integer range for interview-sized inputs.
- The intended solution should avoid brute-force over all possible start times.
Example 1
Input
lights = [4, 2, 7, 1]
Output
4
Explanation
One feasible choice keeps every waiting time at or below 4. Any smaller threshold fails for at least one light, so the minimum possible maximum waiting time is 4.
Example 2
Input
lights = [3, 3, 3]
Output
3
Explanation
All lights have the same synchronized requirement, so the best possible maximum waiting time is 3.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.