P4816.区间列表的交集(非hot100)
题目描述
给定两个由若干个 闭区间 组成的列表，分别为 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，且不需要输出后续区间。
样例1
输入：
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
输入：
2 0
1 3
5 9
输出：
0
样例3
输入：
0 2
4 8
10 12
输出：
0
样例4
输入：
1 1
1 7
3 10
输出：
1
3 7
数据范围
- 0≤n,m≤1000
- n+m≥1
- 0≤starti<endi≤109
- 0≤startj<endj≤109
- 对于同一个区间列表中的相邻区间，保证前一个区间的右端点小于后一个区间的左端点。
