|
| 1 | +/** |
| 2 | + * @param {number[][]} a Array of intervals of a. |
| 3 | + * @param {number[][]} b Arra of intervals of b. |
| 4 | + * @return {number[][]} Intersection of intervals. |
| 5 | + * @summary Interval List Intersection {@link https://leetcode.com/problems/interval-list-intersections/} |
| 6 | + * @description Given two list of intervals, return their intersection. |
| 7 | + * Space O(m+n) - Maximum of size of both arrays. |
| 8 | + * Time O(m+n) - Maximum of size of both arrays. |
| 9 | + */ |
| 10 | +const intervalIntersection = (a, b) => { |
| 11 | + const answer = []; |
| 12 | + let [indexA, indexB] = [0, 0]; |
| 13 | + |
| 14 | + while (indexA < a.length && indexB < b.length) { |
| 15 | + const commonStart = Math.max(a[indexA][0], b[indexB][0]); |
| 16 | + const commonEnd = Math.min(a[indexA][1], b[indexB][1]); |
| 17 | + |
| 18 | + if (commonStart <= commonEnd) { |
| 19 | + answer.push([commonStart, commonEnd]); |
| 20 | + } |
| 21 | + |
| 22 | + if (a[indexA][1] < b[indexB][1]) indexA++; |
| 23 | + else indexB++; |
| 24 | + } |
| 25 | + |
| 26 | + return answer; |
| 27 | +}; |
0 commit comments