Khoảng nhỏ nhất phủ K danh sách (Smallest Range Covering Elements from K Lists) trong C++

Cho k danh sách số nguyên đã sắp xếp. Tìm khoảng [a,b] nhỏ nhất (theo độ dài, rồi theo a) chứa ít nhất 1 phần tử từ mỗi danh sách.

Ví dụ

[[4,10,15,25,26],[0,9,14,20],[5,18,24,30]] → [14,18].

Thuật toán K-way Merge + Min-Heap

Giữ con trỏ cho mỗi list. Min-heap lưu (giá_trị, list_id). Biến curMax theo dõi max hiện tại. Lặp: lấy min, cập nhật best range với curMax. Tăng con trỏ list đó, push phần tử mới, cập nhật curMax. Dừng khi một list hết.

Chương trình C++

#include <bits/stdc++.h>
using namespace std;

struct Cmp {
    bool operator()(pair<int,int> a, pair<int,int> b) {
        return !(a.first < b.first);
    }
};

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int n = nums.size();
        vector<int> ptr(n,0);
        priority_queue<pair<int,int>, vector<pair<int,int>>, Cmp> pq;
        int curMax = INT_MIN;
        for(int i=0;i