Algorithm for finding the number of intersections of segments in a sequence (list)?

Question

C++ / C#

You can write an algorithm that is minimal in complexity (time) to find the number of intersections of segments in

a sequence
( list )

Answer 1

Get an array of zeros. For each segment, make +1 to the coordinate of its left end and -1 to the coordinate following the right end.
Then walk through the array from left to right, maintaining the counter. Add the value of the array to the counter and output the value of the counter.
This is if you need to output the entire array, as in the example. I don’t know the specifics of your task, maybe it will be more efficient to put pairs {coordinate, + -1} into the array and sort. Then, in the same way, go around from left to right while supporting the counter.

Answer 2

If I understand the data types correctly, iterating over the list with a normal check counter+= left<=x<=rightwill be the fastest, taking into account the speed of allocating and freeing memory.