Solution: Interval List Intersections

Explore how to compute the intersection of two sorted lists of intervals efficiently by using two pointers. Understand the step-by-step process to identify overlapping intervals, update pointers based on interval end times, and return the combined intersections. This lesson helps you implement a solution with linear time complexity and constant space usage.

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., intervalLista and intervalListb, 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:

intervalLista[i] = [start_i, end_i]
intervalListb[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$ intervalLista.length, intervalListb.length $\leq 1000$
intervalLista.length $+$ intervalListb.length ...