LeetCode986. Intersection of interval lists

This paper is finally updated at 484 Days ago, , The information may have developed or changed .

One 、 Ideas

This interval problem , In two lists , Compare with each other . use Double pointer It's the realization of this process .

There are two cases , Intersect and disjoint . Intersection ,end Take the maximum of the two intervals . When they don't intersect , See which interval is big , Current end Is the maximum of a small interval . Next pair start,end Take the larger interval .

When does the pointer move ？ According to the maximum value of the two current intervals , The small pointer moves forward . Because we have been comparing the two intervals , So it tends to go forward with two pointers .

Two 、 problem

Given two by some Closed interval A list of components ,firstList and secondList , among firstList[i] = [starti, endi] and  secondList[j] = [startj, endj] . Each interval list is paired Disjoint Of , also It's sorted .

Back here The intersection of two interval lists .

Formally , Closed interval [a, b]（ among  a <= b） For real numbers  x  Set , and  a <= x <= b .

Of two closed intervals intersection Is a set of real numbers , Or it's an empty set , Either it's a closed interval . for example ,[1, 3] and [2, 4] The intersection of is [2, 3] .

Example 1：

 Input ：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
 Output ：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Copy

Example 2：

 Input ：firstList = [[1,3],[5,9]], secondList = []
 Output ：[]

Copy

Example 3：

 Input ：firstList = [], secondList = [[4,8],[10,12]]
 Output ：[]

Copy

Example 4：

 Input ：firstList = [[1,7]], secondList = [[3,10]]
 Output ：[[3,7]]

Copy

Tips ：

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= starti < endi <= 109
• endi < starti+1
• 0 <= startj < endj <= 109
• endj < startj+1

Related Topics

• Double pointer

\n

• 132
• 0

3、 ... and 、 Code

public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
            ArrayList<int[]> list = new ArrayList<>();
            int pointer = 0;
            int pointer1 = 0;
            while (pointer < firstList.length && pointer1 < secondList.length) {
                int n1 = Math.min(firstList[pointer][1], secondList[pointer1][1]);
                int n0 = Math.max(firstList[pointer][0], secondList[pointer1][0]);
                if (n1 >= n0) {
                    list.add(new int[]{n0, n1});
                }
                if (firstList[pointer][1] > secondList[pointer1][1]) {
                    pointer1++;
                } else {
                    pointer++;
                }
            }
            return list.toArray(new int[list.size()][]);
        }

Copy

Post Views: 260