4

I had a question regarding how I should go about determining overlaps of three ranges in Python without using any existing libraries :

For instance if I have three ranges as (10,20)(15,25)(18,30), how should I go about finding overlaps between them ?

My answer should be (18,19,20)

Any help would be much appreciated. Thanks !

user1418321
  • 1,191
  • 2
  • 9
  • 6
  • 1
    Also, what do you mean by those given ranges? A range object in Python (`range(10, 20)`) goes to less than the second value, not including, so the expected output would be `(18, 19)`. – Gareth Latty May 25 '12 at 22:01
  • [Duplicate](http://stackoverflow.com/questions/2953967/built-in-function-for-computing-overlap-in-python) – Steve May 25 '12 at 22:12
  • @Steve Not a duplicate, that question asks for specifically **two** ranges, while this question asks for **three**. While it's easy to extrapolate out, it's not a duplicate. Obviously, a general answer (as given here) is a better option. – Gareth Latty May 25 '12 at 22:14

2 Answers2

8

The overlap goes from the highest start point to the lowest end point:

ranges = [(10,20), (15,25), (18,30)]
starts, ends = zip(*ranges)
result = range(max(starts), min(ends) + 1)

Test:

>>> print(*result)
18 19 20
Reinstate Monica
  • 4,568
  • 1
  • 24
  • 35
  • Thanks a lot. However, I have many such ranges (about a million of them). i.e there are 3 ranges, but there are about million such comparisons to make. Could you tell me a computationally fast method of comparing million such ranges. – user1418321 May 28 '12 at 00:06
  • It takes about 2 seconds on my PC. Unless you are actually creating the ranges as lists (using Python 2.x and not using `xrange`, for example) **and** the results are **huge** this will be fast. If you have to create the actual lists and they are huge, no method will help. – Reinstate Monica May 28 '12 at 13:22
4

While WolframH's answer is the best answer for this case, a more general solution for finding overlaps is available, given you don't need to worry about repeated elements, which is to use sets and their intersection operation.

>>> set(range(10, 21)) & set(range(15, 26)) & set(range(18, 31))
{18, 19, 20}

Or, as a more general solution:

ranges = [(10, 20), (15, 25), (18, 30)]
set.intersection(*(set(range(start, finish+1)) for start, finish in ranges))
Community
  • 1
  • 1
Gareth Latty
  • 86,389
  • 17
  • 178
  • 183
  • 1
    Nice, and you don't even need `reduce`: `set.intersection(*(set(range(start, finish+1)) for start, finish in ranges))`. – Reinstate Monica May 26 '12 at 11:43
  • @WolframH Nice, I did not know that `set.intersection()` accepted multiple sets, that's awesome. I always feel dirty whenever I have to resort to `reduce()`. Edited. – Gareth Latty May 26 '12 at 11:46