In a Meta-style feed aggregation service, multiple independently sorted streams must be combined into one globally sorted result. Given k sorted integer lists, merge them into a single sorted list.
Implement a function that takes lists, where lists[i] is a sorted list of integers in non-decreasing order, and returns a single list containing all values from every input list in non-decreasing order.
lists: List[List[int]]List[int]Example 1
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]Example 2
lists = [[], [0], [-2, 7, 9]][-2,0,7,9]0 <= k <= 10^40 <= len(lists[i]) <= 10^4-10^9 <= lists[i][j] <= 10^910^5.Aim for a solution better than flattening and re-sorting all values when k is much smaller than the total number of elements.
lists = [[1,4,5],[1,3,4],[2,6]]Output[1,1,2,3,4,4,5,6]WhyThe smallest front element is repeatedly chosen from the three sorted lists until all elements are consumed.lists = [[], [0], [-2, 7, 9]]Output[-2,0,7,9]WhyThe empty list is ignored, and the remaining sorted lists are merged into one sorted result.lists = [[5],[5],[5]]Output[5,5,5]WhyDuplicate values are preserved, and each occurrence appears in the final merged output.0 <= k <= 10^40 <= len(lists[i]) <= 10^4-10^9 <= lists[i][j] <= 10^9Each list is sorted in non-decreasing orderThe total number of elements across all lists is at most 10^5def merge_k_sorted_lists(lists):