986 Interval List Intersections

Leetcode

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] 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]]

Example 2:

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

---

一次比较两个 list 的数据片段。取出相交的部分。这两个数据段中结尾坐标大的那个也许还可以和其他的相交。

public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    LinkedList<int[]> list=new LinkedList<>();
    int i1=0, i2=0;
    while(i1<firstList.length && i2<secondList.length){
        if(firstList[i1][1]<secondList[i2][0]){
            i1++;
        } else if(secondList[i2][1]<firstList[i1][0]){
            i2++;
        } else {
            int begin=Math.max(firstList[i1][0], secondList[i2][0]);
            int end1 = firstList[i1][1], end2 = secondList[i2][1];
            int end=Math.min(end1, end2);
            list.add(new int[]{begin, end});
            if(end1>end2){
                i2++;
            } else {
                i1++;
            }
        }
    }
    int[][] arr=new int[list.size()][];
    list.toArray(arr);
    return arr;
}