Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesReviewsAbout
Language
EnglishTürkçe

Intervals

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Heap & Top K →

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumintervals

Interval List Intersections

Problem (restated)

Two lists of closed intervals, each list pairwise disjoint and sorted. Return the intersection intervals of the two lists.

Intuition

Two pointers. Intersection of A[i] and B[j] is [max(starts), min(ends)] if nonempty. Advance the interval that ends first.

Approaches

Two-pointer merge of sorted lists

Tested only
Time O(m + n)Space O(1) extra

Idea. Sorted + disjoint guarantees linear scan without missing overlaps.

Walkthrough. [[0,2],[5,10],[13,23],[24,25]] ∩ [[1,5],[8,12],[15,24],[25,26]] → [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Trade-offs. Binary search per interval is worse when both lists are long.

Solution
export function intervalIntersection(
  firstList: number[][],
  secondList: number[][],
): number[][] {
  const res: number[][] = [];
  let i = 0, j = 0;
  while (i < firstList.length && j < secondList.length) {
    const lo = Math.max(firstList[i]![0]!, secondList[j]![0]!);
    const hi = Math.min(firstList[i]![1]!, secondList[j]![1]!);
    if (lo <= hi) res.push([lo, hi]);
    if (firstList[i]![1]! < secondList[j]![1]!) i++;
    else j++;
  }
  return res;
}

export function intervalIntersection(
  firstList: number[][],
  secondList: number[][],
): number[][] {
  const res: number[][] = [];
  let i = 0, j = 0;
  while (i < firstList.length && j < secondList.length) {
    const lo = Math.max(firstList[i]![0]!, secondList[j]![0]!);
    const hi = Math.min(firstList[i]![1]!, secondList[j]![1]!);
    if (lo <= hi) res.push([lo, hi]);
    if (firstList[i]![1]! < secondList[j]![1]!) i++;
    else j++;
  }
  return res;
}

Template connection

Interval two-pointer sweep.

Reflection