In a 1D space, find if 2 segments intersect or not is frequenly implemented in simple collision detection. 1D segment intersection detection can be extended into 2D rectangle intersection detection and 3D box intersection detection. Many games have to use these to detect if 2 object intersects. Sometimes, details like how much space is intersected are also essential for many game.

1D segment detection is super easy.
suppose there is a segment a, it have 2 points, one is x1, the other is x2. Then there is segment b, also with 2 points, y1 and y2. x1<=x2 and y1<=y2. Then, if x1<=y2 and y1<=x2, then the 2 segment intersects with each other.

The function in both C++ and PHP

function intersectsegment($a,$b){
if($a[0]<=$b[1]&&$a[1]>=$b[0]){
return 1;
}
return 0;
}

struct segment{
int x1, x2;
};
int intersectsegment(segment a, segment b){
if(a.x1<=b.x2&&a.x2>=b.x1){
return 1;
}
return 0;
}

In theory, this is the fastest algorithm possible for finding the intersection between 2 segments.

Ahh, what a weak opponent... I don't even have the time to use my powerful algorithms...
Time to tackle what I was here for:
Boss-- Find all the overlaps between set A, a few segments and set B, a huge amount of segments.

The naive idea: loop though each one of the set A segment with each one in set B. Suppose set B have n segments, because set B is a lot larger than A. The naive algorithm runs in Θ(n) time constantly.
The source code for the naive algorithm is on the attachment. For simplicity, I only counted how many intersections there are without returning the intersected segments.

If you test the source code, you will find if you take out

std::sort(b, b+size);

intersection detection will run slower. If anyone know the reason, please comment, thx in advance.

I have a lot more better algorithm. Meet one of them now :)
First sort the array of segments by their smaller value(x1).
Then, create a larger segment outside 2 adjacent smaller segments and create even larger segment covers the 2 large segments. Do the same operations until there is only one large segment left.
The large segments can be created with a function like this:

segment largegment(segment a, segment b){
segment tmp;
tmp.x1 = min(a.x1,b.x1);
tmp.x2 = max(a.x2,b.x2);
return tmp;
}

Start comparing segments in set A with the largest segments in segment B. if overlaps, compare with the 2nd level, then 3rd level until a point where both smaller segments does not overlap or loop till the smallest segments. If a large segment does not overlap, every smaller segments under the large segment is no longer useful.

The running time for best case(no overlap) will be Ω(1), worst case O(n) and most cases, it's Θ(log n).
In worst case, it actually slower than the naive algorithm, since it preform all the calculation in the naive algorithm and to calculate intersect for all the larger segments.

Oh, it's not over, this is only part 1. Some of my algorithmic predator are still waiting to kill its prey...