Practice/Meta/Leetcode 986. Interval List Intersections

Leetcode 986. Interval List Intersections

CodingMust

Problem

You are given two lists of closed intervals. Each list is sorted by start time and contains non-overlapping intervals (pairwise disjoint). Your task is to find all the intersections between intervals from the first list and intervals from the second list.

An intersection occurs when two intervals share at least one common point. For example, intervals [3, 7] and [5, 9] intersect at [5, 7].

Return a sorted list of all intersection intervals.

Requirements

1. Each input list contains intervals sorted by their start times
2. Within each list, intervals do not overlap with each other
3. Return all non-empty intersections in sorted order
4. Each interval is represented as [start, end] where start ≤ end
5. Intervals are closed, meaning they include both endpoints

Constraints

• 0 ≤ firstList.length, secondList.length ≤ 1000
• firstList[i].length == 2
• secondList[i].length == 2
• 0 ≤ start_i < end_i ≤ 10^9
• The intervals in each list are sorted and non-overlapping
• Aim for O(m + n) time complexity where m and n are the lengths of the two lists

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

Explanation:

• [0,2] and [1,5] overlap at [1,2]
• [5,10] and [1,5] overlap at [5,5]
• [5,10] and [8,12] overlap at [8,10]
• [13,23] and [15,24] overlap at [15,23]
• [24,25] and [15,24] overlap at [24,24]
• [24,25] and [25,26] overlap at [25,25] `

Example 2:

` Input: firstList = [[1, 3], [5, 7]] secondList = [[4, 4], [8, 10]]

Output: []

Explanation: No intervals overlap between the two lists `

Example 3:

` Input: firstList = [[1, 10]] secondList = [[2, 3], [5, 6], [8, 9]]

Output: [[2, 3], [5, 6], [8, 9]]

Explanation: The single interval [1,10] contains all intervals from the second list `