<p>You are given two lists of closed intervals, <code>firstList</code> and <code>secondList</code>, where <code>firstList[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> and <code>secondList[j] = [start<sub>j</sub>, end<sub>j</sub>]</code>. Each list of intervals is pairwise <strong>disjoint</strong> and in <strong>sorted order</strong>.</p>

<p>Return <em>the intersection of these two interval lists</em>.</p>

<p>A <strong>closed interval</strong> <code>[a, b]</code> (with <code>a &lt;= b</code>) denotes the set of real numbers <code>x</code> with <code>a &lt;= x &lt;= b</code>.</p>

<p>The <strong>intersection</strong> 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 <code>[1, 3]</code> and <code>[2, 4]</code> is <code>[2, 3]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/01/30/interval1.png" style="width: 700px; height: 194px;" />
<pre>
<strong>Input:</strong> firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
<strong>Output:</strong> [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> firstList = [[1,3],[5,9]], secondList = []
<strong>Output:</strong> []
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= firstList.length, secondList.length &lt;= 1000</code></li>
	<li><code>firstList.length + secondList.length &gt;= 1</code></li>
	<li><code>0 &lt;= start<sub>i</sub> &lt; end<sub>i</sub> &lt;= 10<sup>9</sup></code></li>
	<li><code>end<sub>i</sub> &lt; start<sub>i+1</sub></code></li>
	<li><code>0 &lt;= start<sub>j</sub> &lt; end<sub>j</sub> &lt;= 10<sup>9</sup> </code></li>
	<li><code>end<sub>j</sub> &lt; start<sub>j+1</sub></code></li>
</ul>

class Solution {
    // Facebook followup: Do it using binary search where m << n
    
    int findIndex(int j, vector<vector<int>>& B, vector<int>& interval)
    {
        if (B[j][1] >= interval[0])
            return j;
        
        int l = j, r = B.size() - 1;
        
        while (l < r)
        {
            int m = l + (r-l)/2;
            
            if (B[m][1] < interval[0])
                l = m+1;
            else
                r = m;
        }
        
        return l;       // this can be invalid i.e. B[l][1] < interval[0]
    }
    
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {                  // Complexity: O(mlogn + n)
        int m = A.size(), n = B.size(), j = 0;
        
        if (m > n)
            return intervalIntersection(B, A);
        
        vector<vector<int>> res;
        
        for (vector<int>& I : A)
        {
            j = findIndex(j, B, I);
                    
            while (j<n && I[1] >= B[j][0] && B[j][1] >= I[0])                           // [[1,8],[16,20]]   =>   [[2, 8]]
            {                                                                           // [[2,11],[12,13]]
                vector<int> merged = { max(I[0], B[j][0]), min(I[1], B[j][1])  };
                
                if (res.empty() || res.back()[1] < merged[0])
                    res.push_back(merged);
                else
                    res.back()[1] = merged[1];
                
                if (B[j][1] <= I[1])
                    j++;
                else // I[1] < B[j][1]
                    break;
            }
            
            if (j == n)                                 // Note:
                break;
        }
        
        return res;
    }
    
    
    
/*  // Complexity: O(m+n)
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res;
        
        int i=0, j=0, m = A.size(), n = B.size();
        
        while (i<m && j<n)
        {
            if (A[i][1] < B[j][0])
                i++;
            else if (B[j][1] < A[i][0])
                j++;
            else // intersecting
            {
                int lb = max(A[i][0], B[j][0]),
                    rb = min(A[i][1], B[j][1]);
                
                res.push_back({lb, rb});
                
                if (rb == A[i][1])
                    i++;
                
                if (rb == B[j][1])
                    j++;
            }
        }
        
        return res;
    }
    
    
    // Fastest
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
        vector<vector<int>> res;
        
        for (int i=0, j=0; i<A.size() && j<B.size(); A[i][1] < B[j][1] ? i++ : j++)
        {
            int lb = max(A[i][0], B[j][0]),
                rb = min(A[i][1], B[j][1]);
            
            if (lb <= rb)
                res.push_back({lb, rb});
        }
        
        return res;
    }                                                                                           */
};
22800