Solution: Interval List Intersections
Explore how to compute the intersection of two sorted lists of closed intervals efficiently. Understand the optimized approach that uses two pointers to traverse both lists, identify overlapping intervals by comparing start and end times, and return their intersections with linear time complexity. This lesson helps you develop skills to solve interval intersection problems commonly seen in coding interviews.
We'll cover the following...
Statement
Given two lists of interval_list_a and interval_list_b, return the intersection of the two interval lists.
Each interval in the lists has its own start and end time and is represented as [start, end]. Specifically:
interval_list_a[i] = [starti, endi]interval_list_b[j] = [startj, endj]
The intersection of two closed intervals i and j is either:
An empty set, if they do not overlap, or
A closed interval
[max(starti, startj), min(endi, endj)]if they do overlap.
Also, each list of intervals is pairwise disjoint and in sorted order.
Constraints:
...