## Algorithm

Problem Name: 986. Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

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 are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

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

Example 2:

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

Constraints:

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= starti < endi <= 109
• endi < starti+1
• 0 <= startj < endj <= 109
• endj < startj+1

## Code Examples

### #1 Code Example with C Programming

Code - C Programming

typedef struct {
int **p;
int *c;
int n;
int sz;
} res_t;
void add2res(res_t *res, int x, int y) {
int *buff = malloc(2 * sizeof(int));
//assert(buff);
buff[0] = x; buff[1] = y;
if (res->sz == res->n) {
if (res->sz == 0) res->sz = 10;
else res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int *));
res->c = realloc(res->c, res->sz * sizeof(int));
//assert(res->p);
}
res->p[res->n] = buff;
res->c[res->n ++] = 2;
}
int _min(int a, int b) {
if (a  <  b) return a;
return b;
}
int _max(int a, int b) {
if (a > b) return a;
return b;
}
int** intervalIntersection(int** A, int ASize, int* AColSize, int** B, int BSize, int* BColSize, int* returnSize, int** returnColumnSizes){
res_t res = { 0 };
int i, j, x, y;
int *a, *b;
i = 0, j = 0;
while (i  <  ASize && j < BSize) {
a = A[i]; b = B[j];
x = _max(a[0], b[0]);
y = _min(a[1], b[1]);

if (x  < = y) add2res(&res, x, y);

if (a[1] > b[1]) j ++;
else i ++;
}

*returnColumnSizes = res.c;
*returnSize = res.n;

return res.p;
}
Copy The Code &

Input

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

Output

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

### #2 Code Example with Java Programming

Code - Java Programming

class Solution {
public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> list = new ArrayList<>();
int idxOne = 0;
int idxTwo = 0;
while (idxOne  <  firstList.length && idxTwo < secondList.length) {
int maxStart = Math.max(firstList[idxOne][0], secondList[idxTwo][0]);
int minEnd = Math.min(firstList[idxOne][1], secondList[idxTwo][1]);
if (maxStart  < = minEnd) {
}
if (minEnd == firstList[idxOne][1]) {
idxOne++;
} else {
idxTwo++;
}
}
int[][] result = new int[list.size()][2];
return list.toArray(result);
}
}
Copy The Code &

Input

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

Output

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

### #3 Code Example with Javascript Programming

Code - Javascript Programming

const intervalIntersection = function (A, B) {
const intersection = []
let i = (j = 0)
while (i < A.length && j < B.length) {
const min = Math.max(A[i][0], B[j][0])
const max = Math.min(A[i][1], B[j][1])
if (min <= max) intersection.push([min, max])
A[i][1] > B[j][1] ? j++ : i++
}
return intersection
}
Copy The Code &

Input

cmd
firstList = [[1,3],[5,9]], secondList = []

Output

cmd
[]

### #4 Code Example with Python Programming

Code - Python Programming

class Solution:
def intervalIntersection(self, A: List[Interval], B: List[Interval]) -> List[Interval]:
i = j = 0
res = []
while i < len(A) and j < len(B):
s = max(A[i].start, B[j].start)
e = min(A[i].end, B[j].end)
if s <= e:
res.append(Interval(s, e))
if A[i].end < B[j].end:
i += 1
elif A[i].end == B[j].end:
i += 1
j += 1
else:
j += 1
return res
Copy The Code &

Input

cmd
firstList = [[1,3],[5,9]], secondList = []

Output

cmd
[]

### #5 Code Example with C# Programming

Code - C# Programming

using System;
using System.Collections.Generic;

namespace LeetCode
{
public class _0986_IntervalListIntersections
{
public int[][] IntervalIntersection(int[][] A, int[][] B)
{
var result = new List < int[]>();
int i = 0, j = 0;

while (i  <  A.Length && j < B.Length)
{
var lo = Math.Max(A[i][0], B[j][0]);
var hi = Math.Min(A[i][1], B[j][1]);
if (lo  < = hi)
result.Add(new int[] { lo, hi });

if (A[i][1] < B[j][1])
i++;
else
j++;
}

return result.ToArray();
}
}
}
Copy The Code &

Input

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

Output

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