interval_list_intersections
1# @leet start 2class Solution: 3 def intervalIntersection( 4 self, firstList: list[list[int]], secondList: list[list[int]] 5 ) -> list[list[int]]: 6 """ 7 This question asks us to find the interval list intersections between two 8 lists of intervals where both lists are sorted. 9 10 We can do this by going through both lists and seeing if there's any overlap 11 in between our left and right pointers. If there is an overlap, we add it 12 to our result array. Calculating overlap is [max(l[0], r[0]), min(l[1], r[1])] 13 However, note that we might have lists like: 14 [5, 15] 15 [5, 10], [10, 15] 16 Where the overlap would be [5, 10], [10, 15]. 17 So, when we choose to increment a pointer, we always want to increment the 18 pointer that ends sooner. This is because the other pointer that ends later 19 may still have some matching intervals that come after the other pointer. 20 So, we use the end of of both pointers to find out what to increment. 21 """ 22 i, j, m, n = 0, 0, len(firstList), len(secondList) 23 res = [] 24 25 while i < m and j < n: 26 (l_start, l_end), (r_start, r_end) = firstList[i], secondList[j] 27 if (l_start <= r_start and l_end >= r_start) or ( 28 r_start <= l_start and r_end >= l_start 29 ): 30 res.append([max(l_start, r_start), min(l_end, r_end)]) 31 if l_end < r_end: 32 i += 1 33 else: 34 j += 1 35 36 return res 37 38 39# @leet end 40def test(): 41 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def intervalIntersection( 5 self, firstList: list[list[int]], secondList: list[list[int]] 6 ) -> list[list[int]]: 7 """ 8 This question asks us to find the interval list intersections between two 9 lists of intervals where both lists are sorted. 10 11 We can do this by going through both lists and seeing if there's any overlap 12 in between our left and right pointers. If there is an overlap, we add it 13 to our result array. Calculating overlap is [max(l[0], r[0]), min(l[1], r[1])] 14 However, note that we might have lists like: 15 [5, 15] 16 [5, 10], [10, 15] 17 Where the overlap would be [5, 10], [10, 15]. 18 So, when we choose to increment a pointer, we always want to increment the 19 pointer that ends sooner. This is because the other pointer that ends later 20 may still have some matching intervals that come after the other pointer. 21 So, we use the end of of both pointers to find out what to increment. 22 """ 23 i, j, m, n = 0, 0, len(firstList), len(secondList) 24 res = [] 25 26 while i < m and j < n: 27 (l_start, l_end), (r_start, r_end) = firstList[i], secondList[j] 28 if (l_start <= r_start and l_end >= r_start) or ( 29 r_start <= l_start and r_end >= l_start 30 ): 31 res.append([max(l_start, r_start), min(l_end, r_end)]) 32 if l_end < r_end: 33 i += 1 34 else: 35 j += 1 36 37 return res
def
intervalIntersection( self, firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
4 def intervalIntersection( 5 self, firstList: list[list[int]], secondList: list[list[int]] 6 ) -> list[list[int]]: 7 """ 8 This question asks us to find the interval list intersections between two 9 lists of intervals where both lists are sorted. 10 11 We can do this by going through both lists and seeing if there's any overlap 12 in between our left and right pointers. If there is an overlap, we add it 13 to our result array. Calculating overlap is [max(l[0], r[0]), min(l[1], r[1])] 14 However, note that we might have lists like: 15 [5, 15] 16 [5, 10], [10, 15] 17 Where the overlap would be [5, 10], [10, 15]. 18 So, when we choose to increment a pointer, we always want to increment the 19 pointer that ends sooner. This is because the other pointer that ends later 20 may still have some matching intervals that come after the other pointer. 21 So, we use the end of of both pointers to find out what to increment. 22 """ 23 i, j, m, n = 0, 0, len(firstList), len(secondList) 24 res = [] 25 26 while i < m and j < n: 27 (l_start, l_end), (r_start, r_end) = firstList[i], secondList[j] 28 if (l_start <= r_start and l_end >= r_start) or ( 29 r_start <= l_start and r_end >= l_start 30 ): 31 res.append([max(l_start, r_start), min(l_end, r_end)]) 32 if l_end < r_end: 33 i += 1 34 else: 35 j += 1 36 37 return res
This question asks us to find the interval list intersections between two lists of intervals where both lists are sorted.
We can do this by going through both lists and seeing if there's any overlap in between our left and right pointers. If there is an overlap, we add it to our result array. Calculating overlap is [max(l[0], r[0]), min(l[1], r[1])] However, note that we might have lists like: [5, 15] [5, 10], [10, 15] Where the overlap would be [5, 10], [10, 15]. So, when we choose to increment a pointer, we always want to increment the pointer that ends sooner. This is because the other pointer that ends later may still have some matching intervals that come after the other pointer. So, we use the end of of both pointers to find out what to increment.
def
test():