K Cặp có tổng nhỏ nhất

import heapq
def k_smallest_pairs_opt(nums1, nums2, k):
    res = []; minH = [[nums1[0] + nums2[0], 0, 0]]
    visit = set([(0, 0)])
    while minH and len(res) < k:
        s, i, j = heapq.heappop(minH)
        res.append([nums1[i], nums2[j]])
        if i + 1 < len(nums1) and (i + 1, j) not in visit:
            heapq.heappush(minH, [nums1[i+1] + nums2[j], i + 1, j])
            visit.add((i + 1, j))
        if j + 1 < len(nums2) and (i, j + 1) not in visit:
            heapq.heappush(minH, [nums1[i] + nums2[j+1], i, j + 1])
            visit.add((i, j + 1))
    return res

def k_smallest_pairs_brute(nums1, nums2, k):
    res = []
    for n1 in nums1:
        for n2 in nums2: res.append([n1, n2])
    res.sort(key=lambda x: x[0] + x[1])
    return res[:k]