这道题的核心做法是 双指针。
因为两个区间列表内部都满足:
给定两个由若干个 闭区间 组成的列表,分别为 firstList 和 secondList。
每个区间列表内部的区间都是两两不相交的,并且已经按照区间起点从小到大排序。
请你求出这两个区间列表的所有交集。
形式上,闭区间 [a,b] 表示所有满足 a≤x≤b 的实数 x。
两个闭区间的交集要么为空,要么仍然是一个闭区间。例如,[1,3] 和 [2,4] 的交集为 [2,3]。
第一行输入两个整数 n 和 m,分别表示第一个区间列表和第二个区间列表中的区间数量。
接下来 n 行,每行输入两个整数 starti 和 endi,表示第一个区间列表中的一个闭区间 [starti,endi]。
接下来 m 行,每行输入两个整数 startj 和 endj,表示第二个区间列表中的一个闭区间 [startj,endj]。
保证每个区间列表内部的区间两两不相交,并且已经按照区间起点从小到大排序。
输出两个区间列表的所有交集。
第一行输出一个整数 k,表示交集区间的数量。
接下来 k 行,每行输出两个整数 l 和 r,表示一个交集区间 [l,r]。
如果不存在交集,则第一行输出 0,且不需要输出后续区间。
输入:
4 4
0 2
5 10
13 23
24 25
1 5
8 12
15 24
25 26
输出:
6
1 2
5 5
8 10
15 23
24 24
25 25

输入:
2 0
1 3
5 9
输出:
0
输入:
0 2
4 8
10 12
输出:
0
输入:
1 1
1 7
3 10
输出:
1
3 7