Interval List Intersections (Leetcode 986)

Difficulty: Medium Link: Leetcode 986

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.

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

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]]
Input: firstList = [[1,3],[5,9]], secondList = []
Output: []
Input: firstList = [], secondList = [[4,8],[10,12]]
Output: []
Input: firstList = [[1,7]], secondList = [[3,10]]
Output: [[3,7]]

Solution

The input lists are already sorted which guarantees that next interval would be equal or later than the current interval , so we do not have to order on the basis of start/end times. If we think about the possible scenarios, there are only three cases. Either two would overlap and first interval starts before second or second comes before first, in both the cases, we need to find the overlapping range to the result. Also, the intervals might not even intersect.

Possible overlap cases

From the figure, it is clear what for two overlapping intervals, the start of one interval <= end of previous interval. We can follow a two-pointer approach and iterate over the two lists. For an overlapping interval, the start point would be the value coming later in list1 and list2 ( Max(Interval1.start , Interval2.start) ). The end point is the interval closing first among the first and second list intervals ( Min(Interval1.end, interval2.end) ). We also have to increment the pointers and the lesser intervals should be incremented since in a sorted list, the higher values have more chances of overlaps. We append the results in a 2D array and return ultimately the output.

Code

Swift

class Solution {
func intervalIntersection(_ firstList: [[Int]], _ secondList: [[Int]]) -> [[Int]] {
var output = [[Int]]()
var p1 = 0, p2 = 0
while p1<firstList.count , p2<secondList.count{
let first = firstList[p1]
let second = secondList[p2]
let start = max(first[0],second[0])
let end = min(second[1],first[1])
if start <= end {
output.append([start,end])
}
if second[1] > first[1]{
p1 += 1
}
else{
p2 += 1
}
}
return output
}
}

Python

class Solution:
def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
ans = []
i = j = 0
while i < len(A) and j < len(B):
# Let's check if A[i] intersects B[j].
# lo – the startpoint of the intersection
# hi – the endpoint of the intersection
lo = max(A[i][0], B[j][0])
hi = min(A[i][1], B[j][1])
if lo <= hi:
ans.append([lo, hi])
# Remove the interval with the smallest endpoint
if A[i][1] < B[j][1]:
i += 1
else:
j += 1
return ans

Java

class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> ans = new ArrayList();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
// Let's check if A[i] intersects B[j].
// lo – the startpoint of the intersection
// hi – the endpoint of the intersection
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi)
ans.add(new int[]{lo, hi});
// Remove the interval with the smallest endpoint
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return ans.toArray(new int[ans.size()][]);
}
}

Complexity Analysis

We iterate both the list one by one therefore if M is the length of first length and N is second list’s length, total operations becomes O(M+N). For the space, we are storing the intersections and in the worst case, all the items can be slotted end to end (Next Interval’s start == previous interval’s end). In that case, total M + N – 1 elements would be stored or O(M + N).

Time = O(M + N) // M = Length of first list, N = length of second list

Space = O(M + N)

Links

Merge Intervals | GeeksForGeeks

Leave a Reply

Your email address will not be published. Required fields are marked *