interval_list_intersections [Paul's Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Interval List Intersections ======

I dedicated a whole page to this problem.

This was asked at of me at an interview and I flubbed it. I attempted this
problem a month after the interview and I still didn't fully get it, and made
numerous mistakes which I want to analyze.

Here is the algorithm I came up with:

{{:pasted:20200819-195351.png?500}}

Here is the code that I wrote:

<code cpp>
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    
    int pa = 0, pb = 0;
    
    vector<vector<int>> out;
    vector<int> last = {-1, -1};
    vector<int> cur;
    
    while(pa < A.size() || pb < B.size() )
    {   // get next interval
        // deal with pointers going out of bounds
        if      ( pa >= A.size()  )         { cur = B[pb++];   }
        else if ( pb >= B.size()  )         { cur = A[pa++];   }
        else if ( A[pa][0] <= B[pb][0] )    { cur = A[pa++];   }
        else                                { cur = B[pb++];   }
        
        // check if next intersects with last
        int min_end   = min(last[1], cur[1]);
        int max_start = max(last[0], cur[0]);
        
        if(min_end >= max_start)
        {
            out.push_back({max_start, min_end});
        }
        last = cur;
    }
  return out; 
}
</code>

Here's a review of the original algorithm with the mistakes I made.

{{:pasted:20200819-200725.png?500}}

Algorithm:

{{:pasted:20200819-205425.png?500}}

Code:
<code cpp>
vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
    
    int pa = 0, pb = 0;
    vector<vector<int>> out;
    
    // if any pointer goes out of bounds, we are done checking!
    while( pa < A.size() && pb < B.size() )
    {
        int min_end   = min(A[pa][1], B[pb][1]);
        int max_start = max(A[pa][0], B[pb][0]);
        
        if(max_start <= min_end)
        {
            out.push_back({max_start,min_end});
        }
        
        // push forward the pointer to the element with the smallest end
        if(A[pa][1] < B[pb][1])
            pa++;
        else
            pb++;
    }
    return out;
}
</code>