6
\$\begingroup\$
def getIntersection(set_item1, set_item2):
    (l11, l12) = set_item1
    (l21, l22) = set_item2
    if (l11 > l21 and l11 < l22) or (l12 > l21 and l12 < l22) or (l21 > l11 and l21 < l12) or (l22 > l11 and l22 < l12):
        if l11 > l21:
            start = l11
        else: start = l21

        if l12 > l22:
            end = l22
        else:
            end = l12
        return (start ,end)
    return None

def returnInersection(set1, set2):
    for l1 in set1:
        for l2 in set2:
            ret = getIntersection(l1, l2)
            if ret:
                print ret

I think above one works fine but it runs in O(n2). Is there any better solution?

Example input can be set1=[(1, 6), (10, 15), (20, 30)] and set2=[(2, 5), (7, 13)].

\$\endgroup\$
2
  • \$\begingroup\$ This is a really good first question. You should feel good about yourself. \$\endgroup\$ Oct 21, 2017 at 3:59
  • 1
    \$\begingroup\$ Are input intervals guaranteed to not overlap within each set? Are the sets guaranteed to be given in increasing order of lower bound? Do or don't (1, 2) and (2, 3) overlap? (What would two non-disjoint sets be?) \$\endgroup\$
    – greybeard
    Nov 20, 2017 at 9:11

2 Answers 2

3
\$\begingroup\$

borrowing for Oscar Smith's solution

If the intervalsX are ordered, you can simply use:

def return_intersections(intervals1, intervals2):
    iter1 = iter(intervals1)
    iter2 = iter(intervals2)

    interval1 = next(iter1)
    interval2 = next(iter2)

    while True:
        intersection = getIntersection(interval1, interval2)
        if intersection:
            yield intersection
            try:
                if intersection[1] == interval1[1]:
                    interval1 = next(iter1)
                else:
                    interval2 = next(iter2)
            except StopIteration:
                return

        try:
            while interval1[0] > interval2[1]:
                interval2 = next(iter2)
            while interval2[0] > interval1[1]:
                interval1 = next(iter1)
        except StopIteration:
            return
list(return_intersections(set1, set2))
[(2, 5), (10, 13)]

in Python pre-3.5 all the try-except boilerplate wouldn't be necessary, but pep-476 changed this.

The advantage of this is that it works for any stream of ordered intervals. So intervalsX can be a generator, list, tuple,...

\$\endgroup\$
2
\$\begingroup\$

The really low hanging fruit here is improving getIntersection Rather than special casing everything, you can simply say that the intersection is the distance between the max of the mins, and the min of the maxes (if the end is greater than the start). While we're at it, we might as well clean up some of the naming issues.

def getIntersection(interval_1, interval_2):
    start = max(interval_1[0], interval_2[0])
    end = min(interval_1[1], interval_2[1])
    if start < end:
        return (start, end)
    return None

This is simpler, cleaner, and faster to boot.

The next thing we can do to speed things up from here is to take note of two facts that occur because the intervals are disjoint.

  1. If intervals1[i] intersects with intervals2[j], intervals1[i+1] does not intersect with intervals2[j].
  2. If intervals1[i] does not intersect with intervals2[j], it does not intersect with intervals2[j+1].

Your original returnInersection code is O(n^2) because it searches the cross product of the two lists. Each of the above rules limits almost half of the space, and if you use both, you only check for O(n) intersections (basically the diagonal) This code does that.

def returnInersection(intervals1, intervals2):
    start = 0
    for interval1 in intervals1:
        found_yet = False
        for j in range(start, len(intervals2)):
            intersection = getIntersection(interval1, intervals2[j])
            if intersection:
                print(intersection)
                found_yet = True
                start += 1
            elif found_yet:
                break

I'm sure there are still ways to speed this up, but it is at least algorithmically optimal.

\$\endgroup\$
1
  • \$\begingroup\$ I would prefer to yield the intersection instead of print. That way, the user of this algorithm can do something with the result. You could also do for interval2 in intervals2[start:]: instead of the for j in range(start, len(intervals2)):. If interval1[0] > interval2[1] without there being an intersection you can increment start too \$\endgroup\$ Jan 19, 2018 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.