Imagine you’re interacting with Alexa. When you command Alexa to “acquire a certain item”, it begins to retrieve information from a variety of sources, which we’ll refer to as “catalogues”. Each catalogue responds with a sorted list of potential matches. Your task is to write a program that can consolidate these sorted lists into one coherent list.
Example – When you ask Alexa to buy bananas, it retrieves information from Prime, Whole Foods, Pantry, etc. Each of these catalogues returns a sorted list of potential matches, and our goal is to consolidate these sorted lists into one coherent list.
这道题本质上是经典的多路归并问题：给定多个已经排好序的列表，需要把它们合并成一个整体有序的结果。最直接的做法是使用最小堆维护每个列表当前的最小候选元素，每次弹出堆顶并把同一列表中的下一个元素继续加入堆中，这样可以在保证全局有序的同时控制时间复杂度。面试中也可以讨论朴素逐个合并的做法，但在列表数量较多时，堆方案通常更高效、更符合线上评估对大数据量的要求。
