leetcode

0 class Solution {

1 typedef tuple<int, int, int> tpl;

2

3 public:

4 vector<vector<int>> kSmallestPairs(const vector<int> &nums1, const vector<int> &nums2, int k) {

5 priority_queue<tpl, vector<tpl>, greater<tpl>> pq;

6 vector<vector<int>> res;

7 res.reserve(k);

8

9 for (int i = 0; i < min(k, (int)nums1.size()); i++)

10 pq.push({nums1[i] + nums2[0], i, 0});

11

12 while (k-- && !pq.empty()) {

13 auto [sum, i, j] = pq.top();

14 pq.pop();

15 res.push_back({nums1[i], nums2[j]});

16 if (j == nums2.size() - 1) continue;

17 pq.push({nums1[i] + nums2[j + 1], i, j + 1});

18 }

19 return res;

20 }

21 };