86. 区间列表的交集

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。

返回这 两个区间列表的交集 。

形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。

两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

难度：🌟🌟🌟

示例 1：

输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

示例 2：

输入：firstList = [[1,3],[5,9]], secondList = []
输出：[]

示例 3：

输入：firstList = [], secondList = [[4,8],[10,12]]
输出：[]

示例 4：

输入：firstList = [[1,7]], secondList = [[3,10]]
输出：[[3,7]]
 
提示：

• 0 <= firstList.length, secondList.length <= 1000
• firstList.length + secondList.length >= 1
• 0 <= start_i < end_i <= 10⁹
• end_i < start_i+1
• 0 <= start_j < end_j <= 10⁹
• end_j < start_j+1

题解

我们用[a1, a2] 和 [b1, b2] 分别表示在 firstList 和 secondList 中的两个区间，使用 p1 和 p2 分别表示 [a1, a2] 和 [b1, b2] 下标。
当 a2 < b2 时，则计算交集，然后 p1 指向下一个区间；
否则，计算交集，然后 p2 指向下一个区间;
直到 p1 或 p2 有一个遍历到了数组末尾，循环停止。

代码实现

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
	p1, p2 := 0, 0
	var res [][]int
	for p1 < len(firstList) && p2 < len(secondList) {
		a := firstList[p1]
		b := secondList[p2]
		if a[1] < b[1] {
			if intersection := calIntersection(a, b); intersection != nil {
				res = append(res, intersection)
			}
			p1++
		} else {
			if intersection := calIntersection(b, a); intersection != nil {
				res = append(res, intersection)
			}
			p2++
		}
	}
	return res
}

func calIntersection(a, b []int) []int {
	x1, y1 := a[0], a[1]
	x2, _ := b[0], b[1]
	if x2 > y1 {
		return nil
	}
	if x2 >= x1 {
		return []int{x2, y1}
	}
	// x2 < x1
	return []int{x1, y1}
}