Interval List Intersections
Explore how to determine intersections between two sorted lists of closed intervals. Understand the problem constraints, learn to identify overlapping intervals, and implement solutions to return their intersections efficiently within coding interviews.
We'll cover the following...
Statement
Given two lists of 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:
intervalListA.length,intervalListB.lengthintervalListA.lengthintervalListB.lengthstartiendiendistarti + 1startjendjendjstart[j + 1]
Examples
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
From the following interval arrays, find their intersecting intervals.
First array = [[2, 6], [7, 9], [10, 13], [14, 19], [20, 24]]
Second array = [[1, 4], [6, 8], [15, 18]]
[[1, 4], [6, 8], [13, 18]]
[[2, 4], [6, 6], [7, 8], [15, 18]]
[[2, 4], [6, 8], [15, 18]]
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.
Try it yourself
Implement your solution in the following coding playground.
package mainfunc intervalsIntersection(intervalsA [][]int, intervalsB [][]int) [][]int {// Replace this placeholder return statement with your codereturn make([][]int, 0)}