Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
interval_list_intersections [2020/08/19 19:53] 127.0.0.1 external edit |
interval_list_intersections [2020/08/19 20:58] (current) |
||
|---|---|---|---|
| Line 9: | Line 9: | ||
| Here is the algorithm I came up with: | Here is the algorithm I came up with: | ||
| + | {{: | ||
| Here is the code that I wrote: | Here is the code that I wrote: | ||
| Line 40: | Line 41: | ||
| } | } | ||
| return out; | return out; | ||
| + | } | ||
| + | </ | ||
| + | |||
| + | Here's a review of the original algorithm with the mistakes I made. | ||
| + | |||
| + | {{: | ||
| + | |||
| + | Algorithm: | ||
| + | |||
| + | {{: | ||
| + | |||
| + | Code: | ||
| + | <code cpp> | ||
| + | vector< | ||
| + | | ||
| + | int pa = 0, pb = 0; | ||
| + | vector< | ||
| + | | ||
| + | // if any pointer goes out of bounds, we are done checking! | ||
| + | while( pa < A.size() && pb < B.size() ) | ||
| + | { | ||
| + | int min_end | ||
| + | int max_start = max(A[pa][0], | ||
| + | | ||
| + | if(max_start <= min_end) | ||
| + | { | ||
| + | out.push_back({max_start, | ||
| + | } | ||
| + | | ||
| + | // push forward the pointer to the element with the smallest end | ||
| + | if(A[pa][1] < B[pb][1]) | ||
| + | pa++; | ||
| + | else | ||
| + | pb++; | ||
| + | } | ||
| + | return out; | ||
| } | } | ||
| </ | </ | ||