1028. Interval List Intersections

• Difficulty: Medium

• Topics: Two Pointers

• Similar Questions:

  • Merge Intervals

  • Merge Sorted Array

  • Employee Free Time

Problem:

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, 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 is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

Solutions:

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> ret;

        if(A.empty() && B.empty())  return {};

        int posA = 0;
        int posB = 0;

        while (posA < A.size() || posB < B.size()) {
            if (posA == A.size()) {
                merge(ret, B[posB++]);
                continue;
            } 

            if (posB == B.size()) {
                merge(ret, A[posA++]);
                continue;
            }

            if (A[posA][0] <= B[posB][0]) {
                merge(ret, A[posA++]);
            } else {
                merge(ret, B[posB++]);
            }
        }

        ret.pop_back();
        return ret;
    }

private:
    void merge(vector<vector<int>>& ret, vector<int>& interval) {
        if (ret.empty()) {
            ret.push_back(interval);
            return;
        }

        vector<int> pending = ret.back();
        ret.pop_back();
        int overLapLeft = max(pending[0], interval[0]);
        int overLapRight = min(pending[1], interval[1]);

        if (overLapLeft <= overLapRight) {
            ret.push_back({overLapLeft, overLapRight});
        }

        ret.push_back({min(pending[1], interval[1]), max(pending[1], interval[1])});
    }
};