Intersection of two lists of ranges in Python

intersection of intervals
interval list intersections
find intersecting intervals for 2 lists of overlapping intervals
interval list intersections java
intersection of n ranges
check if two intervals overlap python
find overlapping intervals python
overlap function in python

A friend of mine passed me over an interview question he recently got and I wasn't very happy with my approach to the solution. The question is as follows:

  • You have two lists.
  • Each list will contain lists of length 2, which represent a range (ie. [3,5] means a range from 3 to 5, inclusive).
  • You need to return the intersection of all ranges between the sets. If I give you [1,5] and [0,2], the result would be [1,2].
  • Within each list, the ranges will always increase and never overlap (i.e. it will be [[0, 2], [5, 10] ... ] never [[0,2], [2,5] ... ])

In general there are no "gotchas" in terms of the ordering or overlapping of the lists.

Example:

a = [[0, 2], [5, 10], [13, 23], [24, 25]]
b = [[1, 5], [8, 12], [15, 18], [20, 24]]

Expected output: [[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

My lazy solution involved spreading the list of ranges into a list of integers then doing a set intersection, like this:

def get_intersection(x, y):
    x_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in x] for item in sublist]
    y_spread = [item for sublist in [list(range(l[0],l[1]+1)) for l in y] for item in sublist]
    flat_intersect_list = list(set(x_spread).intersection(y_spread))
...

But I imagine there's a solution that's both readable and more efficient.

Please explain how you would mentally tackle this problem, if you don't mind. A time/space complexity analysis would also be helpful.

Thanks

OP, I believe this solution works, and it runs in O(m+n) time where m and n are the lengths of the lists. (To be sure, make ranges a linked list so that changing its length runs in constant time.)

def intersections(a,b):
    ranges = []
    i = j = 0
    while i < len(a) and j < len(b):
        a_left, a_right = a[i]
        b_left, b_right = b[j]

        if a_right < b_right:
            i += 1
        else:
            j += 1

        if a_right >= b_left and b_right >= a_left:
            end_pts = sorted([a_left, a_right, b_left, b_right])
            middle = [end_pts[1], end_pts[2]]
            ranges.append(middle)

    ri = 0
    while ri < len(ranges)-1:
        if ranges[ri][1] == ranges[ri+1][0]:
            ranges[ri:ri+2] = [[ranges[ri][0], ranges[ri+1][1]]]

        ri += 1

    return ranges

a = [[0,2], [5,10], [13,23], [24,25]]
b = [[1,5], [8,12], [15,18], [20,24]]
print(intersects(a,b))
# [[1, 2], [5, 5], [8, 10], [15, 18], [20, 24]]

Find intersection of intervals given by two lists, Find the intersection or set of ranges that are common to both the lists. Disjoint means no element is common in a list. Example: {1, 4} and {5, 6} are disjoint while {� Python | Intersection of two lists Intersection of two list means we need to take all those elements which are common to both of the initial lists and store them into another list. Now there are various ways in Python, through which we can perform the Intersection of the lists.

Find Intersection of all Intervals, Write a function to get the intersection point of two Linked Lists | Set 2 � Intersection of two arrays in Python ( Lambda expression and filter function )� Python Set intersection() The intersection() method returns a new set with elements that are common to all sets. The intersection of two or more sets is the set of elements that are common to all sets.

Algorithm

Given two intervals, if they overlap, then the intersection's starting point is the maximum of the starting points of the two intervals, and its stopping point is the minimum of the stopping points:

To find all the pairs of intervals that might intersect, start with the first pair and keep incrementing the interval with the lower stopping point:

At most m + n pairs of intervals are considered, where m is length of the first list, and n is the length of the second list. Calculating the intersection of a pair of intervals is done in constant time, so this algorithm's time-complexity is O(m+n).

Implementation

To keep the code simple, I'm using Python's built-in range object for the intervals. This is a slight deviation from the problem description in that ranges are half-open intervals rather than closed. That is,

(x in range(a, b)) == (a <= x < b)

Given two range objects x and y, their intersection is range(start, stop), where start = max(x.start, y.start) and stop = min(x.stop, y.stop). If the two ranges don't overlap, then start >= stop and you just get an empty range:

>>> len(range(1, 0))
0

So given two lists of ranges, xs and ys, each increasing in start value, the intersection can be computed as follows:

def intersect_ranges(xs, ys):

    # Merge any abutting ranges (implementation below):
    xs, ys = merge_ranges(xs), merge_ranges(ys)

    # Try to get the first range in each iterator:
    try:
        x, y = next(xs), next(ys)
    except StopIteration:
        return

    while True:
        # Yield the intersection of the two ranges, if it's not empty:
        intersection = range(
            max(x.start, y.start),
            min(x.stop, y.stop)
        )
        if intersection:
            yield intersection

        # Try to increment the range with the earlier stopping value:
        try:
            if x.stop <= y.stop:
                x = next(xs)
            else:
                y = next(ys)
        except StopIteration:
            return

It seems from your example that the ranges can abut. So any abutting ranges have to be merged first:

def merge_ranges(xs):
    start, stop = None, None
    for x in xs:
        if stop is None:
            start, stop = x.start, x.stop
        elif stop < x.start:
            yield range(start, stop)
            start, stop = x.start, x.stop
        else:
            stop = x.stop
    yield range(start, stop)

Applying this to your example:

>>> a = [[0, 2], [5, 10], [13, 23], [24, 25]]
>>> b = [[1, 5], [8, 12], [15, 18], [20, 24]]
>>> list(intersect_ranges(
...     (range(i, j+1) for (i, j) in a),
...     (range(i, j+1) for (i, j) in b)
... ))
[range(1, 3), range(5, 6), range(8, 11), range(15, 19), range(20, 25)]

How to find the intersection and union of two lists in Python , Here are three functions using set s to remove duplicate entries from a list, find the intersection of two lists, and find the union of two lists. Note� In this python programming tutorial, we will learn how to find the intersection of two lists. The program will create two lists by taking the inputs from the user first. It will then find out the intersection of the lists and print out the result. Algorithm to use : Create two empty list variables. Ask the user to enter the size of both lists.

I'm no kind of python programmer, but don't think this problem is amenable to slick Python-esque short solutions that are also efficient.

Mine treats the interval boundaries as "events" labeled 1 and 2, processing them in order. Each event toggles the respective bit in a parity word. When we toggle to or from 3, it's time to emit the beginning or end of an intersection interval.

The tricky part is that e.g. [13, 23], [24, 25] is being treated as [13, 25]; adjacent intervals must be concatenated. The nested if below takes care of this case by continuing the current interval rather than starting a new one. Also, for equal event values, interval starts must be processed before ends so that e.g. [1, 5] and [5, 10] will be emitted as [5, 5] rather than nothing. That's handled with the middle field of the event tuples.

This implementation is O(n log n) due to the sorting, where n is the total length of both inputs. By merging the two event lists pairwise, it could be O(n), but this article suggests that the lists must be huge before the library merge will beat the library sort.

def get_isect(a, b):
  events = (map(lambda x: (x[0], 0, 1), a) + map(lambda x: (x[1], 1, 1), a)
          + map(lambda x: (x[0], 0, 2), b) + map(lambda x: (x[1], 1, 2), b))
  events.sort()
  prevParity = 0
  isect = []
  for event in events:
    parity = prevParity ^ event[2]
    if parity == 3:
      # Maybe start a new intersection interval.
      if len(isect) == 0 or isect[-1][1] < event[0] - 1:
        isect.append([event[0], 0])
    elif prevParity == 3:
      # End the current intersection interval.
      isect[-1][1] = event[0]
    prevParity = parity
  return isect

Here is an O(n) version that's a bit more complex because it finds the next event on the fly by merging the input lists. It also requires only constant storage beyond inputs and output:

def get_isect2(a, b):
  ia = ib = prevParity = 0
  isect = []
  while True:
    aVal = a[ia / 2][ia % 2] if ia < 2 * len(a) else None
    bVal = b[ib / 2][ib % 2] if ib < 2 * len(b) else None
    if not aVal and not bVal: break
    if not bVal or aVal < bVal or (aVal == bVal and ia % 2 == 0):
      parity = prevParity ^ 1
      val = aVal
      ia += 1
    else:
      parity = prevParity ^ 2
      val = bVal
      ib += 1
    if parity == 3:
      if len(isect) == 0 or isect[-1][1] < val - 1:
        isect.append([val, 0])
    elif prevParity == 3:
      isect[-1][1] = val
    prevParity = parity
  return isect

Python Set intersection() Method, Definition and Usage. The intersection() method returns a set that contains the similarity between two or more sets. Meaning: The returned set contains only� Here are three functions using sets to remove duplicate entries from a list, find the intersection of two lists, and find the union of two lists. Note, sets were introduced in Python 2.4, so Python 2.4 or later is required. Also, the items in the list must be hashable and order of the lists is not preserved.

Answering your question as I personally would probably answer an interview question and probably also most appreciate an answer; the interviewee's goal is probably to demonstrate a range of skills, not limited strictly to python. So this answer is admittedly going to be more abstract than others here.

It might be helpful to ask for information about any constraints I'm operating under. Operation time and space complexity are common constraints, as is development time, all of which are mentioned in previous answers here; but other constraints might also arise. As common as any of those is maintenance and integration with existing code.

Within each list, the ranges will always increase and never overlap

When I see this, it probably means there is some pre-existing code to normalize the list of ranges, that sorts ranges and merges overlap. That's a pretty common union operation. When joining an existing team or ongoing project, one of the most important factors for success is integrating with existing patterns.

Intersection operation can also be performed via a union operation. Invert the sorted ranges, union them, and invert the result.

To me, that answer demonstrates experience with algorithms generally and "range" problems specifically, an appreciation that the most readable and maintainable code approach is typically reusing existing code, and a desire to help a team succeed over simply puzzling on my own.

Another approach is to sort both lists together into one iterable list. Iterate the list, reference counting each start/end as increment/decrement steps. Ranges are emitted on transitions between reference counts of 1 and 2. This approach is inherently extensible to support more than two lists, if the sort operation meets our needs (and they usually do).

Unless instructed otherwise, I would offer the general approaches and discuss reasons I might use each before writing code.

So, there's no code here. But you did ask for general approaches and thinking :D

Find the Intersection of Two Sets of Coordinates and Sort By Colors , If you are a learner and learning Data Stricture and OOP in Python, it may Develop an algorithm that takes two lists of coordinates and returns return [self. sets[i] for i in range(0, len(self.sets)-1) if self.sets[i] == self.sets[i+1]]. Approach #2 : Using Set intersection() This is an efficient method in comparison to the naive approach. We first convert both list of lists into list of tuples using map() because Python sets are compatible with tuples, not lists.

Python Program to Find the Intersection of Two Lists, Here is source code of the Python Program to find the intersection of two lists. + str(x+1) + ":")) alist.append(element) print("For list2:") for x in range(0,n2):� What is the best way in Python to determine what values in two ranges overlap? For example: x = range(1,10) y = range(8,20) (The answer I am looking for would be the integers 8 and 9.) Given a range, x, what is the best way to iterate through another range, y and output all values that are shared by both ranges? Thanks in advance for the help

Interval List Intersections, Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

Interval List Intersections, Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. (Formally� Find Union and Intersection of two unsorted arrays; Union and Intersection of two linked lists | Set-2 (Using Merge Sort) Generate all possible sorted arrays from alternate elements of two given sorted arrays; Set update() in Python to do union of n arrays; Intersection of two arrays in Python ( Lambda expression and filter function )

Comments
  • How is [1, 2] the union of [0, 2] and [1, 5]?
  • You "lazy" solution doesn't even give the expected output.
  • @DimKoim yes I was just giving a peek at where I was going
  • @EliSadoff sorry, intersection. thanks
  • @EliSadoff As a range, the intersection of 0-2 and 1-5 is 1-2
  • How is this O(m+n) when the code includes sorting all successive groups of four numbers?
  • Sorting a list of length four runs in constant time in terms of the lengths of the input lists, and you do this sorting O(m+n) times.
  • I see, each sort is independent of n, so it's constant, that makes sense. Thanks for clarifying.
  • There should not be [[20, 23], [24, 24]] but [[20,24]]. This is exactly where I am stuck and am not able to find a good way to do that.
  • a) the prompt does not specify that's the case & b) compacting the list afterward would not be difficult.
  • And how can you say more correct than the OPs example??
  • The solution you have provided does not handle all cases. What if answer is something like, [[1,3],[4,4],[5,5]], answer should be [[1,5]] and your list compacting will give [[1,4],[4,5]]
  • But it is still not correct :P See if you can handle above case.