Interval Intersection

Problem

Given two lists of closed intervals, each sorted and internally non-overlapping, return every intersection as a list of [start, end] pairs.

Advance two pointers: the intersection is [max of starts, min of ends] when that range is non-empty, then move the pointer whose interval ends first. An overlap that is a single point is included.

Hint

After recording an intersection, discarding the interval that ends earlier is always safe.

Test cases

case 1

in: [[[0,2],[5,10],[13,23],[24,25]],[[1,5],[8,12],[15,24],[25,26]]]

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

case 2

in: [[],[[1,2]]]

expected: []

case 3

in: [[[1,2]],[]]

expected: []

case 4

in: [[[1,5]],[[2,3]]]

expected: [[2,3]]

case 5

in: [[[1,2]],[[2,3]]]

expected: [[2,2]]

Starter codePython

def interval_intersection(first, second):
    # Your code here
    pass

5 test cases · run your code against them in the editor