Compile Ready
Module 4 · Greedy Interval Pattern

Interval List Intersections

MediumProblem 9 of 12 9 min read ~22 min to solve LeetCode
IntervalsTwo PointersGreedyMergeSorting
Asked atGoogleAmazonMicrosoftMetaApple

Problem Statement

You are given two lists of closed intervals, firstList and secondList. Within each list, intervals are pairwise disjoint and sorted by start time. Return the intersection of these two interval lists.

Input

Two integer matrices firstList and secondList, each already sorted by start with no overlaps inside the same list.

Output

An integer matrix containing every intersection interval, in sorted order.

Constraints

  • •0 <= firstList.length, secondList.length <= 1000
  • •firstList[i].length == 2
  • •secondList[j].length == 2
  • •0 <= start <= end <= 10^9
  • •Each input list is pairwise disjoint and sorted by start

Examples

Example 1

Input: 
firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Explanation: Each output interval is the overlap between the current interval from the first list and the current interval from the second list. Touching endpoints such as **5** and **25** count because intervals are closed.

Example 2

Input: 
firstList = [[1,3],[5,9]], secondList = []
Output: []
Explanation: If one list is empty, there is no interval from that list to intersect with the other list.

Example 3

Input: 
firstList = [[1,7]], secondList = [[3,4],[5,6]]
Output: [[3,4],[5,6]]
Explanation: Both intervals in the second list lie inside **[1,7]**, so each one becomes an intersection.

Learning Objectives

  • Use two pointers to merge across two sorted interval lists.
  • Compute an intersection as **[max(startA,startB), min(endA,endB)]**.
  • Advance the interval that ends first and justify why it cannot help later.
  • Handle endpoint-touching intersections correctly for closed intervals.

Intuition

Pattern Recognition

The signal is two sorted interval lists, pairwise disjoint, and return intersections. This is the interval version of merging two sorted arrays. Because each list is already sorted and non-overlapping internally, only the current interval from each list can possibly create the next output intersection.

For two current intervals A and B, the overlap starts at the later start and ends at the earlier end. If max(startA,startB) <= min(endA,endB), that range is a real closed-interval intersection. After processing the pair, the interval with the smaller end is finished forever: every future interval in the other list starts at or after the current one, so the smaller-ending interval cannot intersect anything later. That gives the pointer move.

Common mistakes

  • ×Advancing both pointers after every comparison and skipping intersections when one long interval overlaps multiple shorter intervals.
  • ×Using a strict **start < end** test and missing single-point intersections like **[5,5]**.
  • ×Sorting the input again even though the lists are already sorted and disjoint.
  • ×Building merged unions of both lists instead of directly emitting intersections.

Algorithm Explanation

Key idea

Keep one pointer in each list. For firstList[i] and secondList[j], the intersection candidate is [max(starts), min(ends)]. Emit it when the start is less than or equal to the end. Then advance the pointer whose interval ends first, because that interval cannot overlap any later interval from the other list.

Interval walkthrough

Use firstList = [[0,2],[5,10],[13,23],[24,25]] and secondList = [[1,5],[8,12],[15,24],[25,26]]. Draw the first pair on a number line: A [0,2] and B [1,5] overlap from 1 to 2, so output [1,2] and advance A because it ends at 2. Now A [5,10] touches B [1,5] at 5, so output [5,5] and advance B. The same A [5,10] then overlaps B [8,12] as [8,10]. Each move discards only the interval whose right edge has already passed.

Algorithm

  1. Initialise pointers i = 0 and j = 0 and an empty result list.
  2. While both pointers are inside their lists, read intervals A = firstList[i] and B = secondList[j].
  3. Compute start = max(A.start, B.start) and end = min(A.end, B.end).
  4. If start <= end, append [start,end] to the result.
  5. If A.end < B.end, increment i.
  6. If B.end < A.end, increment j.
  7. If the ends are equal, increment both pointers.
  8. Convert the result list to an int[][] and return it.

Solutions

Solution: Two-pointer interval merge

When to prefer this:

Use this when both interval lists are already sorted and internally disjoint, which makes a linear merge possible.

Compare the current interval from each list. The overlap, if any, is bounded by the later start and the earlier end. After checking it, discard the interval that ends first because it cannot intersect future intervals.

Step-by-step

  1. Start one pointer at the beginning of each list.
  2. For the current pair, compute start = max(startA, startB) and end = min(endA, endB).
  3. Append [start,end] when start <= end.
  4. Advance the pointer whose current interval has the smaller end.
  5. If both intervals end together, advance both pointers.
  6. Continue until either list is exhausted, then return the collected intersections.
Time

O(m + n)

Space

O(k)

Each input interval is advanced at most once. The result stores **k** intersections; aside from output storage, the algorithm uses O(1) extra space.

Java implementation

Loading…

Dry Run

Sample input

firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]].

first intervalsecond intervalcandidateappendadvance
[0,2][1,5][1,2] is valid[1,2]first, because 2 < 5
[5,10][1,5][5,5] is valid[5,5]second, because 5 < 10
[5,10][8,12][8,10] is valid[8,10]first, because 10 < 12
[13,23][8,12][13,12] is invalidnonesecond, because 12 < 23
[13,23][15,24][15,23] is valid[15,23]first, because 23 < 24
[24,25][15,24][24,24] is valid[24,24]second, because 24 < 25
[24,25][25,26][25,25] is valid[25,25]first, because 25 < 26

The pointer with the smaller end always moves past an interval that cannot overlap anything later. The collected intersections are [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]].

Interview Tips

Lead with the sorted-list merge analogy. The strongest sentence is: the next intersection can only come from the two current intervals, and after checking them, the one ending first is exhausted. Be explicit that intervals are closed, so touching endpoints produce valid one-point intersections such as [5,5].

Likely follow-ups

  • How would you intersect more than two sorted interval lists?
  • How would the answer change for half-open intervals **[start,end)**?
  • How would you return the total length of all intersections without storing them?
  • What if intervals inside each input list were not sorted or could overlap?

Similar Problems

Merge Intervals
MediumBoth rely on local overlap tests after intervals are ordered.
Insert Interval
MediumAnother problem where a carried interval is compared against sorted ranges.
Employee Free Time
HardCombines multiple sorted schedules and reasons about gaps between merged busy intervals.
Meeting Rooms
EasyUses sorted intervals and endpoint comparisons to detect conflicts.

Key Takeaways

  • For two intervals, the intersection is bounded by the later start and earlier end.
  • Closed intervals intersect when **maxStart <= minEnd**, including single-point touches.
  • Advance the pointer with the smaller end because that interval cannot help with future intervals.
  • Sorted, disjoint input lists make the solution linear without extra sorting.
Reusable template: Two-list interval merge: compare current intervals, emit the overlap from max start to min end, then advance the interval that ends first.