Merge K Sorted Lists
You are given k sorted lists of integers. Your task is to merge them into a single sorted list. If there are duplicate values across lists, they should appear in the merged list based on their original list's order if possible, otherwise any consistent order is fine. The final merged list should be sorted in non-decreasing order.
Input
The first line contains an integer k, the number of sorted lists. The next k lines each contain a sorted list of integers. An empty line signifies an empty list. Each list is terminated by a newline character.
Output
Print the single merged sorted list of integers, with elements separated by spaces.
Constraints
1 <= k <= 200000. The total number of elements across all lists is at most 200000. Each element is an integer between -10^9 and 10^9.
Example 1
3 1 4 5 1 3 4 2 6
1 1 2 3 4 4 5 6
Merges three lists into a single sorted list.
Example 2
2 10 20 5 15 25
5 10 15 20 25
Merges two lists, including overlapping values.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
3 1 4 5 1 3 4 2 6
2 10 20 5 15 25