Differences

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

--- interval_list_intersections [2020/08/19 19:53]
paul
+++ interval_list_intersections [2020/08/19 20:58] (current)
@@ Line 41: / Line 41: @@
     }
   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>