0986 - Interval List Intersections

0986 - Interval List Intersections

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].

Examples

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

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

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

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

Constraints

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

Java Solution (Two Pointer)

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int j = 0;
        
        while(i < firstList.length && j < secondList.length) {
            int low = Math.max(firstList[i][0], secondList[j][0]);
            int high = Math.min(firstList[i][1], secondList[j][1]);
            
            if(low <= high) 
                result.add(new int[]{low, high});
            
            if (firstList[i][1] < secondList[j][1])
                i++;
            else
                j++;
        }
        return result.toArray(new int[result.size()][]);
    }
}