Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Interval List Intersections

Two sorted lists

Given two sorted lists of intervals, find their intersection.

Example: A = [[0,2],[5,10]], B = [[1,5],[8,12]]. Intersections: [1,2] (from [0,2] and [1,5]), [5,5] (from [5,10] and [1,5]), [8,10] (from [5,10] and [8,12]).

How would you find all intersections efficiently? Naive approach checks all O(n×m)O(n \times m) time using O(n+m)O(n + m) space pairs. The sorted property lets you do better.