1
#include <limits>
2
#include <queue>
3
#include <vector>
4

5
using namespace std;
6

7
struct Item {
8
  int val;
9
  int r;
10
  int c;
11

12
  Item(int val, int r, int c) : val(val), r(r), c(c) {}
13
};
14

15
struct Comp {
16
  bool operator()(const Item &it1, const Item &it2) {
17
    return it2.val < it1.val;
18
  }
19
};
20

21
class Solution {
22
 public:
23
  vector<int> smallestRange(vector<vector<int>> &nums) {
24
    priority_queue<Item, vector<Item>, Comp> pq;
25

26
    int high = numeric_limits<int>::min();
27
    int n = nums.size();
28
    for (int i = 0; i < n; ++i) {
29
      pq.push(Item(nums[i][0], i, 0));
30
      high = max(high, nums[i][0]);
31
    }
32
    int low = pq.top().val;
33

34
    vector<int> res{low, high};
35

36
    while (pq.size() == (size_t)n) {
37
      auto it = pq.top();
38
      pq.pop();
39

40
      if ((size_t)it.c + 1 < nums[it.r].size()) {
41
        pq.push(Item(nums[it.r][it.c + 1], it.r, it.c + 1));
42
        high = max(high, nums[it.r][it.c + 1]);
43
        low = pq.top().val;
44
        if (high - low < res[1] - res[0]) {
45
          res[0] = low;
46
          res[1] = high;
47
        }
48
      }
49
    }
50

51
    return res;
52
  }
53
};