986. Interval List Intersections

// LeetCode URL: https://leetcode.com/problems/interval-list-intersections/
import java.util.ArrayList;

// Definition for an interval.
class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

/**
 * Using modified Merge operation of Morge Sort
 *
 * Refer:
 * https://leetcode.com/problems/interval-list-intersections/discuss/231108/C++-O(n)-"merge-sort"
 *
 * Time Complexity: O(A + B)
 *
 * Space Complexity: O(A + B)
 *
 * A = Length of array A. B = Length of array B.
 */
class Solution {
    public Interval[] intervalIntersection(Interval[] A, Interval[] B) {
        if (A == null || B == null || A.length == 0 || B.length == 0) {
            return new Interval[0];
        }

        ArrayList<Interval> result = new ArrayList<>();
        int i = 0;
        int j = 0;

        while (i < A.length && j < B.length) {
            if (A[i].end < B[j].start) {
                i++;
            } else if (B[j].end < A[i].start) {
                j++;
            } else {
                result.add(new Interval(Math.max(A[i].start, B[j].start), Math.min(A[i].end, B[j].end)));
                if (A[i].end < B[j].end) {
                    i++;
                } else {
                    j++;
                }
            }
        }

        return result.toArray(new Interval[result.size()]);
    }
}