problem statement
Code
I'm solving a problem where I can insert lamps on a street segment [L, R], and later need to answer queries like: “What’s the minimum number of lamps needed to fully cover [L, R]?”
In my solution (which passed all tests), each query walks from L to R using a greedy jump to the farthest lamp covering the current position. In the worst case — like when every lamp covers only one position — this query can walk every single position in [L, R], so O(N) per query.
Since there can be up to Q = N = 2·10⁵ such queries, isn’t the total worst-case complexity O(N²)?
Yet the solution is accepted . Why does it pass if O(N²) time is theoretically possible? Does the test data avoid this case? Or is there something I’m missing in the analysis?
