Interval problem

The so-called interval problem , It's the line segment problem , Let you Merge all segments 、 Find the intersection of line segments wait . There are two main techniques ：

1. Sort . The common sorting method is to sort according to the starting point of the interval , Or sort it in ascending order first , If the starting point is the same , Then sort them in descending order . Of course , If you have to sort by destination , No asymmetric operations , It's the same thing .
2. drawing That is to say, don't be lazy , Do it frequently , How many possibilities are there for the relative position of the two intervals , How should our code handle different relative positions .

Interval covering problem

Leetcode 1288 Delete the covered range

Ask us the question , After removing the covered interval , How many intervals are left , Then we can calculate first , How many are covered , And then subtracting it from the total is the number of remaining intervals .

For this kind of interval problem , If there's no clue , First of all, let's have a look at , For example, we sort in ascending order according to the starting point of the interval ：

After the sorting , Two adjacent intervals may have the following three relative positions ：

For the above three cases , We should do the following ：

1. Situation 1 , We found the coverage .
2. Situation two , Two intervals can be combined , Into a large range .
3. Situation three , The two intervals don't intersect at all .

According to the above situations , We can write the following code ：

int removeCoveredIntervals(int[][] intvs) {
    
    //  In ascending order of the starting point , Start at the same time, in descending order 
    Arrays.sort(intvs, (a, b) -> {
    
        if (a[0] == b[0]) {
    
            return b[1] - a[1];
        }
        return a[0] - b[0]; 
    });

    //  Record the start and end of the merge interval 
    int left = intvs[0][0];
    int right = intvs[0][1];

    int res = 0;
    for (int i = 1; i < intvs.length; i++) {
    
        int[] intv = intvs[i];
        //  Situation 1 , Find the coverage range 
        if (left <= intv[0] && right >= intv[1]) {
    
            res++;
        }
        //  Situation two , Find the intersection , Merge 
        if (right >= intv[0] && right <= intv[1]) {
    
            right = intv[1];
        }
        //  Situation three , Complete disjunction , Update start and end 
        if (right < intv[0]) {
    
            left = intv[0];
            right = intv[1];
        }
    }

    return intvs.length - res;
}

The above is the solution code of this problem , Start in ascending order , The purpose of descending order of endpoints is to prevent the following situations

For these two intervals where the starting point is the same , We need to make sure The long section is above （ In descending order of destination ）, In this way, it will be judged as covering , Otherwise, it will be wrongly judged as intersecting , One less coverage area .

About java Some operations of two-dimensional array

// java Create a 2D array 
int[][] arr = {
    {
    1, 4}, {
    3, 6}, {
    2, 8}};
System.out.println(Arrays.toString(data)); //  Using this method, you can print out what each array in the two-dimensional array is 
System.out.println(arr.length); // 3
int[] arr1 = arr[1];
System.out.println(arr1[0]); // arr1 Itself is an address value , But by taking the specific elements inside , What you can get is the specific value in the array 

java In the middle of lambda function

lambda There are four main examples of function expressions

*   - 1、 No parameters required , The return value is 5 () -> 5
*   - 2、 Receive a parameter ( Numeric type ), Back to its 2 Times value 
*   - 3、 receive 2 Parameters ( Numbers ), And return their difference  (x, y) -> x – y
*   - 4、 receive 2 individual int Type integer , Back to their and   (int x, int y) -> x + y
*   - 5、 Accept one  string  object , And print on the console , No value returned ( Looks like a return void) (String s) -> System.out.print(s)

Interval merging problem

Leetcode 56 topic , Merge range

The general idea to solve the interval problem is to sort first , Then observe the rules .

An interval can be expressed as **[start, end]**, The interval scheduling problem mentioned above , Need to press end Sort , In order to satisfy the nature of greedy choice . And for the interval merging problem , In fact, according to end and start It can be sorted , But for the sake of clarity , We choose to press start Sort .

obviously , For several intersection intervals, the result interval after merging x,x.start It must be in these intersecting intervals start The smallest ,x.end It must be in these intersecting intervals end maximal .

Because it's in order ,x.start Good. Sure , seek x.end And it's easy , It's analogous to finding the maximum value in an array ：

int max_ele = arr[0];
for (int i = 1; i < arr.length; i++) 
    max_ele = max(max_ele, arr[i]);
return max_ele;

Complete code python

# intervals  Form like  [[1,3],[2,6]...]
def merge(intervals):
    if not intervals: return []
    #  By interval  start  Ascending order 
    intervals.sort(key=lambda intv: intv[0])
    res = []
    res.append(intervals[0])

    for i in range(1, len(intervals)):
        curr = intervals[i]
        # res  Reference to the last element in 
        last = res[-1]
        if curr[0] <= last[1]:
            #  Find the biggest  end
            last[1] = max(last[1], curr[1])
        else:
            #  Process the next interval to be merged 
            res.append(curr)
    return res

java edition

class Solution {
    
    public int[][] merge(int[][] intervals) {
    
        LinkedList<int[]> res = new LinkedList<>();
        //  By interval  start  Ascending order 
        Arrays.sort(intervals, (a, b) -> {
    
            return a[0] - b[0];
        });
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
    
            int[] curr = intervals[i];
            // res  Reference to the last element in 
            int[] last = res.getLast();
            if (curr[0] <= last[1]) {
    
                last[1] = Math.max(last[1], curr[1]);
            } else {
    
                //  Process the next interval to be merged 
                res.add(curr);
            }
        }
        // return res.toArray(new int[0][0]);
        return res.toArray(new int[res.size()][];
    }
}

toArray() Convert a collection into an array

Interval intersection problem

Intersection of interval lists

The subject is well understood , Is to let you find intersection , Notice that the intervals are all closed intervals

The ideas to solve interval problems are generally sorted first , In order to operate , But the title says it's in order , So you can use two index pointers in A and B Middle reaches , Find the intersection ,

The code looks something like this ：

# A, B  Form 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

It's not hard to , Let's start with an honest analysis of various situations .

First , For two intervals , We use it [a1,a2] and [b1,b2] It means that A and B Two intervals in , that Under what circumstances do these two intervals not intersect ：

There are only two cases , The condition for writing code is ：

if b2 < a1 or a2 < b1:
    [a1,a2]  and  [b1,b2]  No intersection 

that , Under what circumstances , There is an intersection between the two intervals ？ According to the negation of the proposition , The above logic No proposition Is the condition of intersection ：

It's very simple , Is this Four situations ** nothing more . So think about it next , In these cases , Does intersection have anything in common ？

We were surprised to find , The intersection interval is regular ！ ** If the intersection interval is [c1,c2], that c1=max(a1,b1),c2=min(a2,b2)！** This is the core of finding 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)])
    # ...

The last step , Our pointer i and j Must move forward （ Increasing ） Of , When should we move forward ？

Combined with animation examples That makes sense , Whether to move forward , It just depends on a2 and b2 The size of the relationship ：

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

in summary , Code implementation

Python Code implementation

# A, B  Form like  [[0,2],[5,10]...]
def intervalIntersection(A, B):
    i, j = 0, 0 #  Double pointer 
    res = []
    while i < len(A) and j < len(B):
        a1, a2 = A[i][0], A[i][1]
        b1, b2 = B[j][0], B[j][1]
        #  There is an intersection between two intervals 
        if b2 >= a1 and a2 >= b1:
            #  Calculate the intersection , Join in  res
            res.append([max(a1, b1), min(a2, b2)])
        #  The pointer goes forward 
        if b2 < a2: j += 1
        else:       i += 1
    return res

Java Code implementation

class Solution {
    
    public int[][] intervalIntersection(int[][] A, int[][] B) {
    
        List<int[]> res = new LinkedList<>();
        int i = 0, j = 0;
        while (i < A.length && j < B.length) {
    
            int a1 = A[i][0], a2 = A[i][1];
            int b1 = B[j][0], b2 = B[j][1];

            if (b2 >= a1 && a2 >= b1) {
    
                res.add(new int[]{
    
                        Math.max(a1, b1), Math.min(a2, b2)
                });
            }
            if (b2 < a2) {
    
                j++;
            } else {
    
                i++;
            }
        }
        return res.toArray(new int[0][0]);
    }
}

summary ：

• Interval problems It all looks complicated , A lot of things are difficult to deal with , But in fact, by observing the commonness of different situations, we can find the law , You can handle it with simple code .