Swift Leetcode Series: Interval List Intersections
You can read the full story on The Swift Nerd blog along with other interesting ones.
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].
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.
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.
Complexity Analysis
Time = O(M + N) // M = Length of first list, N = length of second list
Space = O(M + N)
Thank you for reading. If you liked this article and found it useful, share and spread it like wildfire!
You can find me on TheSwiftNerd | LinkedIn | Github