Решение задачи 986 “Interval List Intersections” с LeetCode.

Условие задачи

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].)

Даны два списка интервалов, каждый список содержит непересекающиеся элементы отсортированные по возврастанию.

Необходимо вернуть пересечение этих двух списков.

пример 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.

ограничения

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

Решение

Два итератора

Создаем результирующий массив res.

Создаем два итератора ( один для массива A – adx, второй для B – bdx).

Идем в цикле с условием , что adx и bdx не дошли до конца ( когда закончился один из массивов – значит дальше нет возможных пересечений ).

На каждой итерации цикла считаем start и end предпологаемого массива:

• start – как максимальное из начала двух отрезков из A и B
• end – как минимальное из концов двух отрезков из A и B

Если start <= end, то такой отрезов существует и можно его добавить в результирующий массив.

Проверяем какой и отрезков раньше закончился, и сдвигаем итератор этого отрезка на следующий.

 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
}