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

Interval List Intersections

Explore how to determine intersections between two disjoint, sorted lists of intervals by assessing overlap conditions. Learn to implement efficient C++ solutions that compute interval intersections, a common pattern in coding interviews related to scheduling and time management challenges.

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 IntervalsIntersection.cpp in the following coding playground. You will need the provided supporting code to implement your solution.

C++
usercode > IntervalsIntersection.cpp
vector<vector<int>> IntervalsIntersection(vector<vector<int>> intervalListA, vector<vector<int>> intervalListB)
{
    // Replace this placeholder return statement with your code
    vector<vector<int>> dummyResult;
    return dummyResult; 
}
Interval List Intersections