986. Interval List Intersections

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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: []

Example 3:

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

Example 4:

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

Code

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> res = new ArrayList<>();

        int p1 = 0, p2 = 0;

        while (p1 < firstList.length && p2 < secondList.length) {
            int[] inter1 = firstList[p1];
            int[] inter2 = secondList[p2];

            int end = Math.min(inter1[1], inter2[1]);

            if (inter1[0] < inter2[0]) {
                if (inter2[0] <= inter1[1]) {
                    res.add(new int[]{inter2[0], end});
                }
            } else {
                if (inter1[0] <= inter2[1]) {
                    res.add(new int[]{inter1[0], end});
                }
            }

            if (inter1[1] <= inter2[1]) {
                p1++;
            } else {
                p2++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}