Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Interval List Intersections

Understand how to find intersections between two sorted lists of closed intervals. Learn to compute overlapping intervals correctly by comparing interval boundaries. This lesson helps you develop a methodical approach to solve interval intersection problems commonly asked in coding interviews.

We'll cover the following...

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] = [starti, endi]

  • intervalListb[j] = [startj, endj]

The intersection of two closed intervals i and j is either:

  • An empty set, if they do not overlap, or

  • A closed interval [max(starti, startj), min(endi, endj)] if they do overlap.

Also, each list of intervals is pairwise disjoint and in sorted order.

Constraints:

  • 0≤0 \leq intervalLista.length, intervalListb.length ≤1000\leq 1000

  • intervalLista.length ++ intervalListb.length >=1>=1

  • 0≤0 \leq starti << endi ≤109\leq 10^9

  • endi << starti + 1

  • 0≤0 \leq startj << endj ≤109\leq 10^9

  • endj << start[j + 1]

Examples

canvasAnimation-image
1 / 5

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Interval List Intersections

1.

From the following interval lists, find their intersecting intervals.

First list = [[2, 6], [7, 9], [10, 13], [14, 19], [20, 24]]

Second list = [[1, 4], [6, 8], [15, 18]]

A.

[[1, 4], [6, 8], [13, 18]]

B.

[[2, 4], [6, 6], [7, 8], [15, 18]]

C.

[[2, 4], [6, 8], [15, 18]]

1 / 2

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5
6

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Solution.java
import java.util.*;
class Solution {
    public static int[][] intervalsIntersection(int[][] intervalLista, int[][] intervalListb) {
        // Replace this placeholder return statement with your code
        return new int[][]{};
    }
}
Interval List Intersections