最小区间

题目描述

给定 k 个整数列表，每个列表内部的元素都已经按非递减顺序排好序。

请你找到一个最短的区间 [a, b]（a ≤ b），使得这个区间内至少包含每个列表中的一个元素。

如果有多个长度相同的区间，选择左端点 a 最小的那个。

请输出这个区间的左右端点。

输入格式

第一行一个正整数 k，表示列表的个数。

接下来 k 行，每行第一个整数 m 表示该列表的长度，随后 m 个整数为该列表的元素（保证非递减）。

输出格式

一行两个整数 a 和 b，表示最短区间的左右端点。

样例

3
5 4 10 15 24 26
4 0 9 12 20
4 5 18 22 30

20 24

1
1 1

1 1

3
2 1 2
2 10 11
2 20 21

2 20

样例解释

• 样例 1：区间 [20, 24] 长度 4，覆盖了第一个列表的 24、第二个列表的 20、第三个列表的 22，是最短区间。
• 样例 2：只有一个列表，包含 1 的任意最短区间为 [1, 1]。
• 样例 3：三个列表分别为 {1,2}、{10,11}、{20,21}，区间 [2, 20]（长度 18）覆盖了 2、10（或 11）、20，是最短区间。

数据范围

• 1 ≤ k ≤ 100
• 每个列表长度 1 ≤ m ≤ 20
• 总元素个数 ≤ 2000
• -10^5 ≤ 元素值 ≤ 10^5

提示

把每个列表中的元素连同其所属列表编号合并成一个数组，按值排序，然后用滑动窗口维护当前窗口覆盖了哪些列表（记录每个列表在窗口内出现的次数）。当窗口覆盖全部 k 个列表时，用窗口两端元素值之差更新答案；不断收缩左端点，直到不再覆盖全部列表。时间复杂度 O(N log N)，N 为总元素个数。