Difficulty: Medium Link: Leetcode 986
You are given two lists of closed intervals,
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
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
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]]
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.
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.
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)