986. Interval List Intersections

Problem solution 986 “Interval List Intersections” from LeetCode.

Problem

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]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.

notes

• 0 <= A.length < 1000
• 0 <= B.length < 1000
• 0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9

Solution

Two iterators

 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
28
29
30
31
32
33
34
35
36

func intervalIntersection(A [][]int, B [][]int) [][]int {
    res := make([][]int, 0)
    adx:=0
    bdx:=0

    for adx<len(A) && bdx<len(B) {
        start := max(A[adx][0],B[bdx][0])
        end := min(A[adx][1],B[bdx][1])
        if start<=end {
             res = append(res, []int{start,end})
        }
       
        
        if A[adx][1]>B[bdx][1] {
            bdx++
        } else {
            adx++
        }
    }
    
    return res
}

func min(a,b int) int {
    if a<b {
        return a
    }
    return b
}

func max(a,b int) int {
    if a>b {
        return a
    }
    return b
}