Teaching Kids Programming: Videos on Data Structures and Algorithms
You are given a list of closed intervals l0 and another list of intervals l1. Individually, each list is non-overlapping and are sorted in ascending order. Return the overlap of the two intervals sorted in ascending order.
Constraints
n ≤ 100,000 where n is the length of l0
m ≤ 100,000 where m is the length of l1Example 1
Input
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 l0 = [ [1, 3], [5, 6], [7, 9] ] l1 = [ [1, 4], [5, 7] ] Output [ [1, 3], [5, 6], [7, 7] ] Example 2 Input l0 = [ [1, 3], [5, 6], [7, 9] ] l1 = [ [100, 200] ] Output []l0 = [ [1, 3], [5, 6], [7, 9] ] l1 = [ [1, 4], [5, 7] ] Output [ [1, 3], [5, 6], [7, 7] ] Example 2 Input l0 = [ [1, 3], [5, 6], [7, 9] ] l1 = [ [100, 200] ] Output []
Two Pointer Algorithm to Compute the Interval Overlapping
Let’s go through the intervals from left to right and consider if two intervals are overlapping by checking the max(starts) and min(ends). Then move the pointer which has a smaller end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | class Solution: def solve(self, A, B): ans = [] i = 0 j = 0 while i < len(A) and j < len(B): start = max(A[i][0], B[j][0]) end = min(A[i][1], B[j][1]) if start <= end: ans.append([start, end]) if A[i][1] < B[j][1]: i += 1 else: j += 1 return ans |
class Solution: def solve(self, A, B): ans = [] i = 0 j = 0 while i < len(A) and j < len(B): start = max(A[i][0], B[j][0]) end = min(A[i][1], B[j][1]) if start <= end: ans.append([start, end]) if A[i][1] < B[j][1]: i += 1 else: j += 1 return ans
Time complexity is O(N+M) where N and M are the lengths of two intervals lists – the space complexity is O(1) if we don’t consider the returned list as additional space.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: GoLang: Insert into a Binary Search Tree via Recursion
Next Post: Teaching Kids Programming - Substrings of Size Three with Distinct Characters