Tìm khoảng nhỏ nhất chứa phần tử từ K danh sách đã sắp xếp trong C++

Cho K danh sách đã sắp xếp. Tìm khoảng [a,b] nhỏ nhất (b-a tối thiểu) chứa ít nhất 1 phần tử từ mỗi danh sách.

Ví dụ

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

Output: [14, 18] (chứa 15 từ list 1, 14 từ list 2, 18 từ list 3)

Thuật toán: Min-Heap + Con trỏ

• Khởi tạo min-heap với phần tử đầu của mỗi list. Theo dõi current_max.
• Khoảng hiện tại: [heap.top(), current_max].
• Lặp: lấy min từ heap, cập nhật kết quả nếu khoảng nhỏ hơn. Thay bằng phần tử tiếp theo của list đó. Cập nhật current_max.
• Dừng khi một list hết phần tử.

Triển khai C++

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

struct Comp {
    bool operator()(const pair<int,int>& a, const pair<int,int>& b) {
        return a.first > b.first; // min-heap
    }
};

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>>, Comp> pq;
    int curMax = INT_MIN;
    
    for (int i = 0; i < n; i++) {
        pq.push({nums[i][0], i});
        curMax = max(curMax, nums[i][0]);
    }
    
    int bestL = INT_MIN, bestR = INT_MAX, bestSize = INT_MAX;
    
    while (true) {
        auto [curMin, idx] = pq.top(); pq.pop();
        if (curMax - curMin < bestSize) {
            bestSize = curMax - curMin;
            bestL = curMin; bestR = curMax;
        }
        
        if (++ptr[idx] == nums[idx].size()) break;
        int nextVal = nums[idx][ptr[idx]];
        curMax = max(curMax, nextVal);
        pq.push({nextVal, idx});
    }
    return {bestL, bestR};
}

int main() {
    vector<vector<int>> v = {{4,10,15,25,26}, {0,9,14,20}, {5,18,24,30}};
    auto res = smallestRange(v);
    cout << "[" << res[0] << ", " << res[1] << "]"; // [14, 18]
    return 0;
}

Kết quả

[14, 18]

Độ phức tạp: O(N log K) với N = tổng số phần tử.