Solution: Interval List Intersections

Explore how to solve the interval list intersection problem by iterating through two sorted lists efficiently. Learn to identify overlapping intervals using two pointers, reduce complexity to O(n+m), and understand key implementation steps to return all intersections.

We'll cover the following...

Statement
Solution
- Naive approach
- Optimized approach using intervals

Statement

Given two lists of closed intervalsA closed interval [start, end] (with start <= end) includes all real numbers x such that start <= x <= end., 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] = [start_i, end_i]
interval_list_b[j] = [start_j, end_j]

The intersection of two closed intervals i and j is either:

An empty set, if they do not overlap, or
A closed interval [max(start_i, start_j), min(end_i, end_j)] if they do overlap.

Also, each list of intervals is pairwise disjoint and in sorted order.

Constraints:

$0 \leq$ ...