Subject to introduce

Force buckle 986: leetcode-cn.com/problems/in…

Give two lists of closed intervals, firstList and secondList, where firstList[I] = [Starti, endi] and secondList[j] = [startJ, endJ]. Each interval list is disjoint in pairs and has been sorted.

Returns the intersection of the two interval lists.

Formally, the closed interval [a, b] (where a <= b) represents the set of real numbers x, where a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or closed. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Analysis of the

They’re asking you to find the intersection, and notice that the intervals are closed.

We can use two index Pointers to navigate between A and B to find the intersection. The code looks something like this:

# A, B is like [[0.2], [5.10]... ]def intervalIntersection(A, B):
    i, j = 0.0
    res = []
    while i < len(A) and j < len(B):
        # ...
        j += 1
        i += 1
    return res
Copy the code

B: No, let’s analyze the situation honestly first.

First of all, for the two intervals, we use [A1,a2] and [b1,b2] to represent the two intervals in A and B, so under what circumstances do these two intervals have no intersection:

There are only two cases where the conditional judgment for writing code looks like this:

ifB2 < A1 or A2 < b1: [A1, A2] and [b1, B2] have no intersectionCopy the code

Now, when do these two intervals intersect? According to the negation of the proposition, the above logical negation is the condition for the existence of intersection:

# If the inequality sign is reversed, or becomes andifB2 >= a1 and A2 >= b1: [A1,a2] and [b1,b2] intersectCopy the code

Now, what are the situations where these two intervals intersect? To name one:

It’s easy, isn’t it? There are only four cases. Now, what do these situations have in common?

To our surprise, the intersection is regular! If the intersection interval is [c1,c2], then c1= Max (A1,b1),c2 =min(A2,b2)! This point is at the heart of finding the intersection. Let’s take the code a step further:

while i < len(A) and j < len(B):
    a1, a2 = A[i][0], A[i][1]
    b1, b2 = B[j][0], B[j][1]
    if b2 >= a1 and a2 >= b1:
        res.append([max(a1, b1), min(a2, b2)])
    # ...
Copy the code

In the last step, our Pointers I and j must advance (incrementing). When should they advance?

It is easy to understand whether to move forward depending only on the size relationship between A2 and b2:

while i < len(A) and j < len(B):
    # ...
    if b2 < a2:
        j += 1
    else:
        i += 1
Copy the code

Write code along these lines:

# A, B is like [[0.2], [5.10]... ]def intervalIntersection(A, B):
    i, j = 0.0Res = []while i < len(A) and j < len(B):
        a1, a2 = A[i][0], A[i][1]
        b1, b2 = B[j][0], B[j][1The two ranges intersectifB2 >= a1 and a2 >= b1: add res res.append([Max (a1, b1), min(a2, b2)]if b2 < a2: j += 1
        else:       i += 1
    return res
Copy the code

In summary, interval class problems seem to be complicated, and there are a lot of cases that are difficult to deal with, but in fact, by looking at the commonalities between different cases, you can find patterns that can be dealt with in simple code.