986. Interval List Intersections

leetcode medium

#array#backtracking#csharp#hash-table#intervals#leetcode#math#medium#search#sort#two-pointers

Task

Вам даны два списка закрытых интервалов, firstList и secondList, где firstList[i] = [starti, endi] и secondList[j] = [startj, endj]. Каждый список интервалов является попарно непересекающимся и отсортированным.

Верните пересечение этих двух списков интервалов.

Закрытый интервал [a, b] (где a <= b) обозначает множество действительных чисел x с a <= x <= b.

Пересечение двух закрытых интервалов - это множество действительных чисел, которые либо пусты, либо представлены как закрытый интервал. Например, пересечение [1, 3] и [2, 4] равно [2, 3].

Пример

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]

Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

C# solution

matched/original

public class Solution {
    public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new List<int[]>();
        int i = 0, j = 0;
        
        while (i < firstList.Length && j < secondList.Length) {
            int start = Math.Max(firstList[i][0], secondList[j][0]);
            int end = Math.Min(firstList[i][1], secondList[j][1]);
            
            if (start <= end) {
                result.Add(new int[]{start, end});
            }
            
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return result.ToArray();
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new List<int[]>();
        int i = 0, j = 0;
        
        while (i < firstList.size() && j < secondList.size()) {
            int start = max(firstList[i][0], secondList[j][0]);
            int end = min(firstList[i][1], secondList[j][1]);
            
            if (start <= end) {
                result.push_back(new int[]{start, end});
            }
            
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return result.ToArray();
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int[][] IntervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> result = new List<int[]>();
        int i = 0, j = 0;
        
        while (i < firstList.length && j < secondList.length) {
            int start = Math.max(firstList[i][0], secondList[j][0]);
            int end = Math.min(firstList[i][1], secondList[j][1]);
            
            if (start <= end) {
                result.add(new int[]{start, end});
            }
            
            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }
        
        return result.ToArray();
    }
}

JavaScript solution

matched/original

var intervalIntersection = function(firstList, secondList) {
    let i = 0, j = 0;
    const result = [];
    
    while (i < firstList.length && j < secondList.length) {
        const start = Math.max(firstList[i][0], secondList[j][0]);
        const end = Math.min(firstList[i][1], secondList[j][1]);
        
        if (start <= end) {
            result.push([start, end]);
        }
        
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    
    return result;
};

Python solution

matched/original

def intervalIntersection(firstList, secondList):
    i, j = 0, 0
    result = []

    while i < len(firstList) and j < len(secondList):
        start = max(firstList[i][0], secondList[j][0])
        end = min(firstList[i][1], secondList[j][1])
        
        if start <= end:
            result.append([start, end])
        
        if firstList[i][1] < secondList[j][1]:
            i += 1
        else:
            j += 1
    
    return result

Go solution

matched/original

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
    i, j := 0, 0
    var result [][]int

    for i < len(firstList) && j < len(secondList) {
        start := max(firstList[i][0], secondList[j][0])
        end := min(firstList[i][1], secondList[j][1])
        
        if start <= end {
            result = append(result, []int{start, end})
        }
        
        if firstList[i][1] < secondList[j][1] {
            i++
        } else {
            j++
        }
    }
    
    return result
}

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
}

Explanation

Algorithm

Инициализация указателей:

Завести два указателя i и j, указывающие на начало firstList и secondList соответственно.

Поиск пересечений:

Пока оба указателя находятся в пределах своих списков, выполнить следующие действия:

Найти максимальное начало и минимальный конец текущих интервалов.

Если начало меньше или равно концу, добавить пересечение в результат.

Сдвинуть указатель списка, у которого текущий интервал заканчивается раньше.

Возврат результата:

Вернуть список пересечений.

😎