Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/986.html
986. Interval List Intersections
Level
Medium
Description
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.
Return the intersection of these two interval lists.
(Formally, 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 is either empty, or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].)
Example 1:
Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Note:
0 <= A.length < 10000 <= B.length < 10000 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
Solution
Since the two arrays A and B are already sorted, loop over the two arrays of intervals to obtain the intersections.
Use a list to store the intersections. Initialize index1 and index2 to be both 0. While index1 < A.length and index2 < B.length, obtain interval1 = A[index1] and interval2 = B[index2] and calculate the intersection of interval1 and interval2. If the intersection is not empty, add the intersection to the list. Then move index1 or index2 or both indices forward by 1 step. If an interval has a smaller end value, move the corresponding index forward by 1 step. If both intervals have the same end value, move both indices forward by 1 step.
After all the intersections are obtained, use a 2D array to store the intersections and return.
-
class Solution { public int[][] intervalIntersection(int[][] A, int[][] B) { List<int[]> intersectionList = new ArrayList<int[]>(); int length1 = A.length, length2 = B.length; int index1 = 0, index2 = 0; while (index1 < length1 && index2 < length2) { int[] interval1 = A[index1]; int[] interval2 = B[index2]; int intersectionLow = Math.max(interval1[0], interval2[0]); int intersectionHigh = Math.min(interval1[1], interval2[1]); if (intersectionLow <= intersectionHigh) { int[] curIntersection = {intersectionLow, intersectionHigh}; intersectionList.add(curIntersection); } int high1 = interval1[1], high2 = interval2[1]; if (high1 <= high2) index1++; if (high1 >= high2) index2++; } int size = intersectionList.size(); int[][] intersectionArray = new int[size][2]; for (int i = 0; i < size; i++) { int[] curIntersection = intersectionList.get(i); intersectionArray[i][0] = curIntersection[0]; intersectionArray[i][1] = curIntersection[1]; } return intersectionArray; } } ############ class Solution { public int[][] intervalIntersection(int[][] firstList, int[][] secondList) { List<int[]> ans = new ArrayList<>(); int m = firstList.length, n = secondList.length; for (int i = 0, j = 0; i < m && j < n;) { int l = Math.max(firstList[i][0], secondList[j][0]); int r = Math.min(firstList[i][1], secondList[j][1]); if (l <= r) { ans.add(new int[] {l, r}); } if (firstList[i][1] < secondList[j][1]) { ++i; } else { ++j; } } return ans.toArray(new int[ans.size()][]); } } -
// OJ: https://leetcode.com/problems/interval-list-intersections/ // Time: O(M+N) // Space: O(1) class Solution { public: vector<vector<int>> intervalIntersection(vector<vector<int>>& A, vector<vector<int>>& B) { int M = A.size(), N = B.size(); vector<vector<int>> ans; for (int i = 0, j = 0; i < M && j < N; ) { int s = max(A[i][0], B[j][0]), e = min(A[i][1], B[j][1]); if (s <= e) ans.push_back({ s, e }); if (A[i][1] < B[j][1]) ++i; else ++j; } return ans; } }; -
class Solution: def intervalIntersection( self, firstList: List[List[int]], secondList: List[List[int]] ) -> List[List[int]]: i = j = 0 ans = [] while i < len(firstList) and j < len(secondList): s1, e1, s2, e2 = *firstList[i], *secondList[j] l, r = max(s1, s2), min(e1, e2) if l <= r: ans.append([l, r]) if e1 < e2: i += 1 else: j += 1 return ans ############ # 986. Interval List Intersections # https://leetcode.com/problems/interval-list-intersections/ class Solution: def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: i = j = 0 n, m = len(firstList), len(secondList) res = [] while i < n and j < m: s1, e1 = firstList[i] s2, e2 = secondList[j] s, e = max(s1, s2), min(e1, e2) if s <= e: res.append([s, e]) if e1 <= e2: i += 1 else: j += 1 return res -
func intervalIntersection(firstList [][]int, secondList [][]int) [][]int { m, n := len(firstList), len(secondList) var ans [][]int for i, j := 0, 0; i < m && j < n; { l := max(firstList[i][0], secondList[j][0]) r := min(firstList[i][1], secondList[j][1]) if l <= r { ans = append(ans, []int{l, r}) } if firstList[i][1] < secondList[j][1] { i++ } else { j++ } } return ans } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b } -
function intervalIntersection( firstList: number[][], secondList: number[][], ): number[][] { const n = firstList.length; const m = secondList.length; const res = []; let i = 0; let j = 0; while (i < n && j < m) { const start = Math.max(firstList[i][0], secondList[j][0]); const end = Math.min(firstList[i][1], secondList[j][1]); if (start <= end) { res.push([start, end]); } if (firstList[i][1] < secondList[j][1]) { i++; } else { j++; } } return res; } -
impl Solution { pub fn interval_intersection( first_list: Vec<Vec<i32>>, second_list: Vec<Vec<i32>>, ) -> Vec<Vec<i32>> { let n = first_list.len(); let m = second_list.len(); let mut res = Vec::new(); let (mut i, mut j) = (0, 0); while i < n && j < m { let start = first_list[i][0].max(second_list[j][0]); let end = first_list[i][1].min(second_list[j][1]); if start <= end { res.push(vec![start, end]); } if first_list[i][1] < second_list[j][1] { i += 1; } else { j += 1; } } res } }