多源新闻 Feed 取最新 N 条
Top-N Recent Items From Per-Source News Feeds
开始编码多源新闻 / 社媒情绪聚合的扇入场景:feeds 是 K 条独立的来源流(例如每家新闻商一条、每个社交平台一条),每条都已经按 ts *降序*(最新在前),因为上游采集器为每个来源维护一个固定大小的环形缓冲区,交还的就是最新一端。下游消费者(情绪聚合 / alpha 研究)只想要**全局最新的 n_top 条**,且每条都打上来源标签以保留 lineage:当看到某条 headline 时必须能反指出究竟是哪个来源发的。
朴素方案——把所有 feed 压平、附加 source_id、sorted(..., reverse=True)[:n_top]——是 O(N log N) 且很傻:输入已经按所要方向排好序,且我们也不要全部 N 条,只要前 n_top 条。正确工具是带 early termination 的最大堆 K 路归并。把每条非空 feed 的队首以 (-ts, source_id, 0) 形态压入堆(负的 ts,因为 heapq 是最小堆),然后循环:弹出最小键(= 全局最大 ts)输出、再把该 feed 的下一条压进堆。一旦 emit 满 n_top 条立即停止。整体 O(n_top · log K),与每条 feed 的总长度无关。
请实现 solution(feeds: list[list[list]], n_top: int) -> list[list]。feeds 是 K 条按 ts 降序的来源流,每条记录形如 [ts, headline_id]。返回全局最新的 n_top 条 [ts, headline_id, source_id] 三元组,按 ts 降序、并列时较小 source_id 先输出。
例如 solution([[[100, 11], [80, 12]], [[90, 21], [70, 22]], [[85, 31]]], 3) 返回 [[100, 11, 0], [90, 21, 1], [85, 31, 2]]:全局最新的三条分别来自三个不同来源——feed 0 的 100 最新、feed 1 的 90 次之、feed 2 的 85 第三。feed 0 的 [80, 12] 和 feed 1 的 [70, 22] 因为只要 3 条而被截断。
并列示例:solution([[[50, 1]], [[50, 2]], [[50, 3]]], 2) 返回 [[50, 1, 0], [50, 2, 1]]:三个来源在 ts=50 全部并列,按较小 source_id 稳定决胜,取前 2 条截断。
边界:solution([], 10) 返回 []——没有 feed 也就没什么可输出。solution([[[5, 7]]], 0) 同样返回 []——n_top=0 直接短路、不做任何工作。
约束条件
- 0 ≤ #feeds = len(feeds) ≤ 50
- 每条 feed 的长度 0 ≤ m_i ≤ 1000
- 0 ≤ n_top ≤ 10^4
- 每条 feed 内部按 `ts` *降序*(最新在前);同一 feed 内 ts 并列时保持原顺序
- feeds[i][j] 形如 `[ts, headline_id]`,ts 是 [0, 10^9] 的整数,headline_id 是整数
- K 条 feed 中允许出现空 feed `[]`,必须跳过、不能压进堆
- 返回 `[ts, headline_id, source_id]` 三元组列表(注意 ts 在前、source_id 在最后——source_id 是 `feeds` 中的 0-based 索引),整体按 `ts` 降序;并列时按较小的 `source_id` 优先输出。长度为 min(n_top, 总条数)
- n_top = 0 → []。所有 feed 都为空(或 `feeds == []`) → []。n_top > 总条数 → 全部归并返回
样例
Case 1 · three sources top-3 picks one from each
输入: [[[[100,11],[80,12]],[[90,21],[70,22]],[[85,31]]],3]
期望: [[100,11,0],[90,21,1],[85,31,2]]
全局最新三条恰好一来源一条:feed 0 在 ts=100、feed 1 在 ts=90、feed 2 在 ts=85。feed 0 和 feed 1 的更老条目被 n_top=3 截掉。
Case 2 · all sources tie at single ts truncated
输入: [[[[50,1]],[[50,2]],[[50,3]]],2]
期望: [[50,1,0],[50,2,1]]
三来源都在 ts=50 并列;按较小 source_id 稳定决胜,截断到 2 条。
Case 3 · single feed n_top exceeds length
输入: [[[[100,1],[80,2],[60,3]]],10]
期望: [[100,1,0],[80,2,0],[60,3,0]]
单条 feed 已是最新优先;n_top=10 > 3 所以全部输出,每条都打上 source_id=0。
最近提交
还没有提交记录。
编码区
实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
Case 1 · three sources top-3 picks one from each
输入: [[[[100,11],[80,12]],[[90,21],[70,22]],[[85,31]]],3]
期望: [[100,11,0],[90,21,1],[85,31,2]]
全局最新三条恰好一来源一条:feed 0 在 ts=100、feed 1 在 ts=90、feed 2 在 ts=85。feed 0 和 feed 1 的更老条目被 n_top=3 截掉。
Case 2 · all sources tie at single ts truncated
输入: [[[[50,1]],[[50,2]],[[50,3]]],2]
期望: [[50,1,0],[50,2,1]]
三来源都在 ts=50 并列;按较小 source_id 稳定决胜,截断到 2 条。
Case 3 · single feed n_top exceeds length
输入: [[[[100,1],[80,2],[60,3]]],10]
期望: [[100,1,0],[80,2,0],[60,3,0]]
单条 feed 已是最新优先;n_top=10 > 3 所以全部输出,每条都打上 source_id=0。