The fastest algorithm determine range overlap

Question

I have two sets of range, each range is a pair of integers indicating start and end. What will be the fastest method to determine if there is any overlap between the two ranges?

Thanks.

Answer 1

If they are both sorted by start you can just inspect the first range in both sets, see if they overlaps and if not move to the next item in the set with the least end offset, rinse and repeat till you find an overlap or you are at the end of one set. This would be O(n) if already sorted, O(n log n) otherwise.