Points and segments solution

Question

Task:

Given a set of points on a line and a set of segments on a line. The goal is to compute, for each point, the number of segments that contain this point.

Input Format

The first line contains two non-negative integers \$s\$ and \$p\$ defining the number of segments and the number of points on a line, respectively. The next \$s\$ lines contain two integers \$a_i, b_i\$ defining the \$i\$th segment \$[a_i, b_i]\$. The next line contains \$p\$ integers defining points \$x_1, x_2, \dots, x_p\$.

Constraints

• \$1 \le s, p \le 50000\$
• \$−10^8 \le a_i \le b_i ≤ 10^8\$ for all \$0 \le i \lt s\$
• \$−10^8 \le x_j \le 10^8\$ for all \$0 \le j \lt p\$

Output Format

Output \$p\$ non-negative integers \$k_0, k_1, \dots , k_{p−1}\$ where \$k_i\$ is the number of segments which contain \$x_i\$.

My solution

For each point \$x_i\$ consider a pair (\$x_i, p\$). For each segment \$[a_i, b_i]\$ consider two pairs: (\$ai, 'l'\$) and (\$b_i, r\$) (\$p, l, r)\$ stand for point, left, and right, respectively).

Example: given three points \$x_1 = 5, x_2 = 8, x_3 = 3\$ and two segments \$[a_1, b_1] = [4, 10], [a_2,b_2] = [2, 6]\$. We then create the following list:

\$(5, p), (8, p), (3, p), (4, l), (10, r), (2, l), (6, r)\$

And then we sort it:

\$(2, l), (3, p), (4, l), (5, p), (6, r), (8, p), (10, r)\$

Now, let's scan it from left to right. The first item indicates the beginning of a segment (as it has l). The next is a point and we know that it is covered by one segment. The next item (4,l) indicates that we have the second segment. The next item (5,p) is a point and it is covered by two segments. The next item indicates the end of some segment, and so on.

import sys

def fast_count_segments(starts, ends, points):
    cnt = [0] * len(points)
    segments_num = 0

    listpoints = [(x, 'l') for x in starts]
    listpoints += [(x, 'p') for x in points]
    listpoints += [(x, 'r') for x in ends]

    listpoints.sort(key=lambda x: x[0], reverse=False)

    for p in listpoints:
        if p[1] == 'l':
            segments_num += 1
        elif p[1] == 'r':
            segments_num -= 1
        else:
            cnt[points.index(p[0])] = segments_num

    return cnt

if __name__ == '__main__':
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    n = data[0]
    m = data[1]
    starts = data[2:2 * n + 2:2]
    ends   = data[3:2 * n + 2:2]
    points = data[2 * n + 2:]
    cnt = fast_count_segments(starts, ends, points)
    for x in cnt:
        print(x, end=' ')

Sample

Input:

2 3
0 5
7 10
1 6 11

Output:

1 0 0

For large input, my code run very slow, so I really need some reviews on my solution and my code to help reduce the runtime.

Answer 1

else:
    cnt[points.index(p[0])] = segments_num

Looking up the index of every point here is slow. A quick fix would be to store counts in a dict and traverse it in the correct order afterwards; see how that performs.

cnt = {}
segments_num = 0

else:
    cnt[p[0]] = segments_num

return [cnt[x] for x in points]

It also looks like your solution isn’t quite correct, since the sort could put lefts, rights, and points at the same location in different orders. Since the correct order of left, point, right also happens to be in alphabetical order, you can do another minimal fix and replace this:

listpoints.sort(key=lambda x: x[0], reverse=False)

with this:

listpoints.sort()

That’s a bit of a hack, but for this sort of task, it seems standard to keep the code short (fast to write in a competition?) rather than particularly expressive.

Answer 2

Besides Ryan O'Hara improvements for speed, I'd like to make a few comments that can improve readability.

Using unpacking, you can simplify your indexes management and give meaningful names to your variables:

for position, kind in listpoints:
    if kind == 'l':
        segments_num += 1
    elif kind == 'r':
        segments_num -= 1
    else:
        cnt[position] = segments_num

or

input = sys.stdin.read()
n, m, *data = map(int, input.split())
starts = data[0:2 * n:2]
ends = data[1:2 * n:2]
points = data[-m:]

You can also join the results to improve printing:

cnt = fast_count_segments(starts, ends, points)
print(' '.join(map(str, cnt)))

The last thing is to use abstract value instead of 'l', 'p', 'r' but with meaningful names. It let you have better control over their ordering and potentialy a slightly faster comparison:

BEGIN, POINT, END = range(3)

def fast_count_segments(starts, ends, points):
    cnt = {}
    segments_num = 0
    listpoints = [(x, BEGIN) for x in starts]
    listpoints += [(x, POINT) for x in points]
    listpoints += [(x, END) for x in ends]
    listpoints.sort()

    for position, kind in listpoints:
        if kind == BEGIN:
            segments_num += 1
        elif kind == END:
            ...

I would also usualy advise to build the input incrementaly rather than reading it at once, but for this kind of challenges it doesn't matter that much. Just make sure to not use input as a variable name as it shadows the builtin function.

Answer 3

I know it's been awhile since this was posted, but since I found it, there's sure to be other people who are still dealing with this kind of thing. There's one thing all the previous answerers missed out on that dramatically accelerates this algorithm.

At the top of the fast_count_segments function, insert this line:

pntInd = np.argsort(points)

and just before the for loop, initialize a point counter currPnt=0. Then, in the 'p' condition inside the loop, instead of cnt[points.index(p[0])], use this:

cnt[pntInd[curPnt]]
curPnt += 1

I did a timing test on my implementation of this with segment boundaries and points randomly generated according to the constraints, and with s=p=50000. Results from 1,000 simulations:

Timing Test Results (1000)
Percentiles of Elapsed Time (s): 10%=0.10, Median=0.10, 90%=0.10 (max=0.51).

Not only should this be this \$O((s+p) * log(s+p))\$, but nice and pythonic!

Answer 4

there is a bug in this code:

cnt[points.index(p[0])] = segments_num

If there are more than two equal values (x) in points, only the index of the first value will be returned. For example:

points = [1, 8, 8]
idx = points.index(8)  # idx will always be 1

Therefore, the last element of cnt will never be updated

The correct way is to use dictionary as presented by @Ryan