2
$\begingroup$

On my computer science course's exam I was given the following task:

You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from_i$ and ends at $to_i$. Your task is for each segment count number of other segments that intersects it.

EXAMPLE INPUT:
5
7 8
8 9
0 3
2 7
10 15

EXAMPLE OUTPUT:
2 1 1 2 0

I've implemented the naive algorithm:

def count_intersections(i):
    counter = 0
    for j in range(len(data)):
        if i != j:
            if data[i][0] <= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]
            
            if right[0] <= left[1] <= right[1]:
                counter += 1
            elif left[0] <= right[0] <= left[1]:
                counter += 1
            
    return counter

n = int(input())
data = []
for i in range(n):
    data.append(tuple(map(int, input().split())))

for i in range(n):
    print(count_intersections(i), end = ' ')

As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.

Do you know more efficient solution? Maybe some extraordinal Data Structure?

$\endgroup$
7
  • $\begingroup$ @greybeard thank for your reply. Can you please be more specific? Does this problem actually has a name? $\endgroup$ – Levon Minasian Aug 28 '20 at 9:46
  • $\begingroup$ @LevonMinasian do you have to output the number of intersections for every segment or just for the total sum? (for the total sum there is a better algo) $\endgroup$ – plshelp Aug 28 '20 at 10:47
  • $\begingroup$ No, bro. I need to output the number of intersections for every line segment. $\endgroup$ – Levon Minasian Aug 28 '20 at 10:52
  • $\begingroup$ @LevonMinasian Is only overlapping considered to be an intersection? Or full containment as well? If only overlapping is a considered to be an intersection there is an $O(n\log(n))$ algo but I need more time to write it down properly. $\endgroup$ – plshelp Aug 28 '20 at 13:22
  • $\begingroup$ @greybeard Doesn't it make a big difference that he only has to output the number of intersections of every segment? If you had to report every intersection solely it's apparent that the lower bound is n^2 but if you just have to output the number? $\endgroup$ – plshelp Aug 28 '20 at 13:25
2
$\begingroup$

Let's first assume there is no common boundaries between all segments.

Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$

Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.

$E[i]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.

$A[i]$ will be the $n$-element array to output, which are 0s initially.

Then loop through the list,

for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

The "-1" stands for a segment not counting himself.

This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.

Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example [2, 7] does intersect [7, 8]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

  • first, you only count the opening segments in $open$
  • then, you only update $E[i]$ and $A[i]$ for both opening and closing segments
  • finally, you only count the closing segments in $close$ (that now have $E[i] = 2$)
$\endgroup$
1
  • $\begingroup$ Another way to treat common boundaries is to treat [2,7] as [2,8). Sort the event tuples by pos, then put closing event before opening event. For events with the same pos and type, record their duplicity using a mapping counter. $\endgroup$ – John L. Sep 1 '20 at 18:41
1
$\begingroup$

Edit: By mistake I thought we were working in 2 dimensions, this answer is for the 2d case. (I don't know why plshelp mentioned order statistics tree in his/her deleted answer because I didn't understood it but maybe he/she misunderstood like me.)

We can use a sweep line algorithm. We think of each active segments as a 1d moving point while we are sweeping the plane.

We store the list of active segments in an order statistics tree (as said by plshelp in a now deleted answer) and we use a priority queue of "events". We store in the "events" each start/end of a segment and also the (dynamically added and removed) intersections.

We continuously update for each active segment the time of intersection with the next segment in the list of active segments and store it in the priority queue. When treating an event:

  1. If this is a start or an end, we add or remove the corresponding active segments.
  2. If this is an intersection, we increment the number of intersections and swap the two corresponding segments in the list.

We also update the new times of intersections (removing or adding at most a low bounded number of items in the priority queue).

Notice that when inserting a new segment, the comparison function must use the current time, but the elements already in the list are necessarily sorted even if the comparison function has changed. This algorithm is in $O((n+k)\log(n))$ where $n$ is the number of segments and $k$ is the number of intersections, since the priority queue cannot store more than $3n$ events.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.