Solution: Interval List Intersections

Understand how to solve interval list intersection problems by using two pointers to iterate through sorted lists. Learn to identify overlapping intervals and update pointers based on interval end times. This lesson teaches an efficient O(n + m) time complexity approach to handle interval intersections, essential for coding interviews involving interval patterns.

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 ...