TomoLink
CompaniesZeptoData Structures & AlgorithmsInterval List Intersections
DSA
MediumArray

Interval List Intersections

arraytwo pointerssweep line

Problem Statement

You are given two lists of closed intervals, firstList and secondList , where firstList[i] = [start _i , end _i ] and secondList[j] = [start _j , end _j ] . 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] .

Examples

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 <= start _i < end _i <= 10 ^9
end _i < start _i+1
0 <= start _j < end _j <= 10 ^9
end _j < start _j+1
🤔
Medium
Difficulty
Topic Info
ModuleDSA
CategoryArray
Sub-topicTwo Pointers
Tags
arraytwo pointerssweep line
Navigation
Interval List Intersections [Medium] | Zepto Dsa | TomoLink