This is an old revision of the document!


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.

class Solution {
public:
 
    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; 
    }
};
  • interval_list_intersections.1597865766.txt.gz
  • Last modified: 2020/08/19 19:36
  • by paul