# 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:

Here is the code that I wrote:

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; }

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

Algorithm:

Code:

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; }