0632. Smallest Range Covering Elements from K Lists¶
题目信息¶
- 题号:
0632
- 难度:
Hard
- 主题:
多个有序列表、闭区间覆盖、最短长度、并列规则
- 原题:
- 重点:
区间必须从每个列表至少包含一个元素、先最小化 b-a、长度相同时选择左端点更小的区间
题目重述¶
给定 k 个非空整数列表 nums,每个列表均按非递减顺序排列。寻找闭区间 [a, b],使每个列表中都至少有一个元素落在该区间内。
在所有满足覆盖条件的区间中,优先选择长度 b-a 最小的区间;若多个区间长度相同,返回左端点 a 更小的那个。列表数量位于 [1, 3500],每个列表长度位于 [1, 50],全部元素总数不超过 3500,元素值位于 [-10^5, 10^5]。
自建示例¶
从每个列表选择不同位置的元素:
输入:nums = [[1,9],[4,10],[6,12]]
输出:[9,12]
解释:区间 [9,12] 分别包含 9、10、12,覆盖三个列表且长度为 3;不存在更短的覆盖区间。
最短长度并列时取更小左端点:
输入:nums = [[1,8],[2,9],[3,10]]
输出:[1,3]
解释:[1,3] 与 [8,10] 都覆盖三个列表且长度为 2,因此按规则选择左端点更小的 [1,3]。