How to speed up an algorithm to detect lights that cover a point?-CodePudding

"Assume you have a road (or numberline) with lights over head that light up a section of the numberline. Lights are represented by a 2D array where the light at index i covers from arr[i][0] to arr[i][1] (inclusive).

You are also given a list of points on this line, and for each point, you want to compute how many lights illuminate that point. I want to return a list where list[i] = the number of lights that illuminate point i."

Sample input/output: lights = [[1, 7], [5, 11], [7, 9]], points = [7, 1, 5] should return [3, 1, 2]
I wrote a solution where for each point in points, you loop over the lights array and see how many have lights[i][0] <= point <= lights[i][1]. This solution is too slow (being O(n *k) where n = num. lights and k = num. points). I also tried sorting the lamps and breaking when lamp[i][0] > point, but it still times out. Can anyone think of a faster algorithm to compute this array? I'm stumped on how else to approach this.

CodePudding user response：

This problem is better solved like this:

Get all the changes from the lights array and create an array that has twice its size. It will have tuples of point and light-change. The light change component is 1 or -1, depending on whether that point represents the beginning of the light span or end of it. When it is the end, the point should be one more than found in the lights array, so to indicate that point is still reached by the light, and we should only discount it when moving to the right to the next point.
Sort this result by point. There might be duplicates.
Then accumulate from left to right the light-change values, so adding up all those -1 and 1 from left to right, and storing the intermediate results again with the point where the light-change was found. The final accumulated value will of course be 0.
Optionally make that array unique by point, only keeping the right most of the duplicate points, as those have the right accumulated value to go with it. (I did not do that in below implementation)
Finally use binary search on that array to translate each given point to the number of lights that shine on that point.

Implementation:

from bisect import bisect

def solve(lights, points):
    pairs = sorted((x   i, -i or 1) for changes in lights for i, x in enumerate(changes))
    offsets, changes = zip(*pairs)
    total = 0
    cumul = [0]   [total := total   change for change in changes]
    return [cumul[bisect(offsets, x)] for x in points]

lights = [[1, 7], [5, 11], [7, 9]]
points = [7, 1, 5]
print(solve(lights, points))  # [3, 1, 2]

And here is the version that removes duplicates. It is only of benefit if there really are many duplicate offsets in the cumul list:

def solve(lights, points):
    pairs = sorted((x   i, -i or 1) for changes in lights for i, x in enumerate(changes))
    total = 0
    cumulpairs = [(x, total := total   change) for x, change in pairs]
    # remove duplicates - assuming Python 3.7  with ordered dicts
    offsets, cumul = zip(*dict(cumulpairs).items())
    cumul = [0]   list(cumul)
    return [cumul[bisect(offsets, x)] for x in points]