Intervals Overview

The Intervals pattern is a set of techniques used to handle problems involving ranges of data, such as time intervals [start, end]. The core idea revolves around sorting the intervals based on their start (or end) times to process overlaps efficiently.

Consider the classic problem: Given a collection of intervals, merge all overlapping intervals.

Input: [[1,3], [2,6], [8,10], [15,18]]

We need a way to combine [1,3] and [2,6] into [1,6] while leaving others intact.

A naive approach would be to compare every interval with every other interval to check for overlaps.

For each interval A, iterate through all other intervals B. If they overlap, merge them. Repeat this process until no merges are possible.

Analysis: This requires repeated passes and searching, leading to an O(N²) complexity, which is too slow for large inputs.

Imagine trying to fit puzzle pieces together by randomly picking two pieces and checking if they connect. You might pick [8,10] and [1,3] and see they don't match. Then [15,18] and [2,6]. It's inefficient because you aren't checking in any order.

If we sort the intervals by their start time, we align them linearly. This means for any interval curr, we only need to compare it with the prev interval to check for overlaps. We effectively turn a 2D search problem into a 1D linear scan.