Interval List Intersections

Interval List Intersections is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Greedy Patterns pattern, in the Interval Merging/Scheduling subpattern.

Problem statement

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

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]]

Example 2:

Input: firstList = [[1,3],[5,9]], secondList = [] Output: []

Constraints:

- 0 <= firstList.length, secondList.length <= 1000

- firstList.length + secondList.length >= 1

- 0 <= starti < endi <= 109

- endi < starti+1

- 0 <= startj < endj <= 109

- endj < startj+1

Topics and companies

Topics: Array, Two Pointers, Line Sweep.

Reported in interviews at Facebook, Uber, Apple, Google, Amazon, Bloomberg.

How to practise Interval List Intersections on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N + M), where N = firstList.size() and M = secondList.size(). Each interval from both lists is processed at most once. time and O(K), where K is the number of intersections found (output size). No extra space is used except for the result. space.

Open Interval List Intersections in the code editor, or read the Interval List Intersections editorial for a worked solution with its approach and complexity analysis.

Where Interval List Intersections sits in the DSA pattern sheet

• Greedy Patterns pattern guide
• Interval Merging/Scheduling subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Interval List Intersections

Other problems that use the same Interval Merging/Scheduling and Greedy Patterns techniques:

• Employee Free Time — Hard, same subpattern
• Assign Cookies — Easy, same pattern
• Candy — Hard, same pattern
• Distant Barcodes — Medium, same pattern
• Divide Intervals Into Minimum Number of Groups — Medium, same pattern
• Gas Station — Medium, same pattern