Differences

This shows you the differences between two versions of the page.

--- interval_list_intersections [2020/08/19 19:36]
paul created
+++ interval_list_intersections [2020/08/19 20:58] (current)
@@ Line 3: / Line 3: @@
 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.
+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>
-class Solution {
+vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) {
-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++];   }
-        int pa = 0, pb = 0;
+        // check if next intersects with last
+        int min_end   = min(last[1], cur[1]);
+        int max_start = max(last[0], cur[0]);
-        vector<vector<int>> out;
+        if(min_end >= max_start)
-        vector<int> last = {-1, -1};
+        {
-        vector<int> cur;
+            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]);
-        while(pa < A.size() || pb < B.size() )
+        if(max_start <= min_end)
-        {   // get next interval
+        {
-            // deal with pointers going out of bounds
+            out.push_back({max_start,min_end});
-            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;
+        // push forward the pointer to the element with the smallest end
+        if(A[pa][1] < B[pb][1])
+            pa++;
+        else
+            pb++;
     }
-};
+    return out;
+}
 </code>