How can we find the number of pairs of intersecting ranges on a circular number line? I recently thought of and managed to solve this algorithmic problem:
On a infinite 1-dimensional number line, we have N ranges specified by two distinct integers A and B, such that all A and B are unique. Each pair of integers then represents the starting and ending points of a range on the number line. How many distinct pairs of ranges intersect?

^^ In this example, 4 distinct pairs of segments intersect.
Obviously, there is a O(N^2) brute-force solution: just test all possible pairs in O(1) time each. However, I also thought of a O(NlogN) sweep-line algorithm: treat every A as a &quot;segment start event&quot; and every B as a &quot;segment end event&quot;. Then, keep a variable curr_in_range (originally 0) that stores the current number of segments that we currently see, and then iterate through the events in sorted order of their positions on the number line. Every time we add another segment, add curr_in_range to the answer (because this new segment will intersect with every other segment that we can see) and increment it as well. Every time we remove a segment, decrement curr_in_range. In the end, this gets us the correct answer.
Happy with this algorithm, I decided to tackle a slightly modified version of this problem: What if the number line is circular? As in, it has a specified length L such that the number line contains numbers in the range [0, L)? In this case, each range would still be specified by two distinct integers A and B, but let's just say the range is always counterclockwise starting from A and ending at B. Could we still find the number of pairs of sectors that intersect in less than O(N^2) time in this scenario?
Here's my thought process on this problem:
We should be able to use a very similar algorithm to the one described above. Completely copying it wouldn't work, though, because the sectors can have B &lt; A when it crosses over 0. My idea was to initially have curr_in_range equal to the number of sectors that cross over 0 (instead of just it at 0 like we did in the above algorithm). Then, we could treat every sector as a &quot;sector start event&quot; and a &quot;sector end event&quot;, and do the same process that we did.
However, after extensive analysis, I found why this approach doesn't work. This approach won't work because it overcounts some of the intersections, as sometimes two sectors can intersect in 2 places. This is where I'm stuck.

^^ Our sweep-line algorithm will count 2 distinct pairs that intersect, when there is actually only 1.
But besides this overcounting, I found that this current algorithm isn't doing a single other thing wrong. I coded a O(N^2) brute-force algorithm and tabulated all the distinct pairs that it found, and also tabulated the distinct pairs found for the current algorithm. For every randomly-generated test case, these two tables were the same. In other words, our current algorithm is correctly detecting every intersection there is to be detected, but it just happens to overcount some of them.
So, sorry for a really long post, but my final question is:
Can someone come up with an algorithm that solves this problem? Is my thought process close to a solution or completely off?
This is solvable in $O(n \log n)$ time, too, by considering the complement of the intervals that wrap around and using a suitable data structure.
There are two types of intervals that can appear on a cycle:

Intervals that do not wrap around: e.g., $[0.3,0.5]$ does not wrap around.  In general, this includes all intervals of the form $[a,b]$ with $0\le a \le b \le 1$.

Intervals that wrap around: e.g., $[0.8,0.1]$ wraps around; it is equivalent to $[0.8,1.1]$ or $[0.8,1] \cup [0,0.1]$.  In general, this includes all intervals of the form $[b,a]$ with $0\le a &lt; b \le 1$; each such interval is equivalent to $[b,1] \cup [0,a]$.


Let $A$ denote the set of intervals that do not wrap around, and $B$ the set of intervals that do wrap around.  Also, let $\overline{B}$ denote the complements of the intervals in $B$, i.e., $\overline{B} = \{\overline{b} \mid b \in B\}$.  For instance, the interval $[0.8,0.1]$ wraps around; its complement is $(0.1,0.8)$, which does not wrap around. It is easier to think about intervals that do not wrap around, and this decomposition  will help us to deal only with intervals that do not wrap around.
Now, we will separately count the number of overlaps between (1) an interval in $A$ and an interval in $A$;
(2) an interval in $A$ and an interval in $B$;
(3) an interval in $B$ and an interval in $A$; and
(4) an interval in $B$ and an interval in $B$.
(1) can be counted with your sweepline algorithm, as we don't need to deal with wraparound.  (4) can also be counted in the same way, as two intervals overlap iff their complements overlap.  I will show below how to count (2); case (3) will then follow by symmetry.  This covers all the cases, so it suffices to count up these four cases and sum them up.
Note that intervals $a \in A, b\in B$ overlap iff $a$ is not a subset of $\overline{b}$.  So, it suffices to count the number of pairs $a \in A, \overline{b}\in \overline{B}$ where $a$ is a subset of $\overline{b}$; then you can subtract that from $|A| \cdot |B|$.
To do that, you can use the data structure in Data structure for interval subset queries.  Store all the intervals $\overline{B}$ in the data structure.  Then, for each $a \in A$, count the number of intervals in $\overline{B}$ that $a$ is a subset of.  This can be done in $O(\log n)$ time per query interval $a$, for a total time of $O(n \log n)$.
Therefore, you can count each of the four cases in $O(n \log n)$ time, and thus compute the overall sum in $O(n \log n)$ time as well.  I think.  I encourage you to check my reasoning to make sure I haven't made any mistakes.