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

Interval List Intersections

Understand how to identify and return intersections of two sorted lists of closed intervals. This lesson helps you develop skills to solve interval problems by evaluating overlaps and handling edge cases, preparing you for coding interviews involving interval manipulation tasks.

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., interval_list_a and interval_list_b, 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:

  • interval_list_a[i] = [starti, endi]

  • interval_list_b[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 interval_list_a.length, interval_list_b.length ≤1000\leq 1000

  • interval_list_a.length ++ interval_list_b.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.

Python
usercode > main.py
def intervals_intersection(interval_list_a, interval_list_b):

    

    # Replace this placeholder return statement with your code



    return []
Interval List Intersections