The fastest algorithm determine range overlap

c# .net algorithm overlap
Mavershang picture Mavershang · Jun 8, 2011 · Viewed 9.6k times · Source

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

BrokenGlass picture BrokenGlass · Jun 8, 2011

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.

Related questions

Best way to reverse a string

I've just had to write a string reverse function in C# 2.0 (i.e. LINQ not available) and came up with this: public string Reverse(string text) { char[] cArray = text.ToCharArray(); string reverse = String.Empty; for (int i = cArray.Length - 1; …

Read More
Best way to randomize an array with .NET

What is the best way to randomize an array of strings with .NET? My array contains about 500 strings and I'd like to create a new Array with the same strings but in a random order. Please include a C# example …

Read More
Algorithm to detect overlapping periods

I've to detect if two time periods are overlapping. Every period has a start date and an end date. I need to detect if my first time period (A) is overlapping with another one(B/C). In my case, if …

Read More