Re: Range overlap (with a lot of ranges)

[moritz]

I haven't read the references you posted earlier, so please forgive me if that one was already suggested.

You could store for each location an array of ranges that contain it:

# range A : 1-3
# range B : 5-6

# leads to

my @ranges = [
[],       # 0
['1-3'],  # 1
['1-3'],  # 2
['1-3'],  # 3
[],       # 4
['5-6'],  # 5
['5-6'],  # 6
];

Once this table is built, for every range it's very fast to test which other ranges overlap.

To save memory, you can also use a string in each location, so that if you have ranges 1-5 and 4-6, the entry for for 5 would be 1-5,4-6.

One million strings should fit into memory. If the array is rather sparse, you could also use a hash instead.