LeetCode [632] Smallest Range

You have k lists of sorted integers in ascending order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a,b] is smaller than range [c,d] if b-a < d-c or a < c if b-a == d-c.

Example 1:

Input:[[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
Output: [20,24]
Explanation: 
List 1: [4, 10, 15, 24,26], 24 is in range [20,24].
List 2: [0, 9, 12, 20], 20 is in range [20,24].
List 3: [5, 18, 22, 30], 22 is in range [20,24].

Note:

1. The given list may contain duplicates, so ascending order means >= here.
2. 1 <= k <= 3500
3. -105 <= value of elements <= 105.
4. For Java users, please note that the input type has been changed to List<List<Integer>>. And after you reset the code template, you'll see this point.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { typedef vector<int>::iterator IT; struct comp{ bool operator()(pair<IT, IT> p1, pair<IT, IT> p2){ return *p1.first > *p2.first; } }; public: vector<int> smallestRange(vector<vector<int>>& nums) { int l = INT_MAX, h = INT_MIN; priority_queue<pair<IT, IT>, vector<pair<IT, IT>>, comp> pq; for(auto &v:nums){ l = min(l, v[0]); h = max(h, v[0]); pq.push(pair<IT, IT>(v.begin(), v.end())); } vector<int> ret{l, h}; while(!pq.empty()){ auto next = pq.top(); pq.pop(); if(++next.first==next.second) break; pq.push(next); l = *pq.top().first; h = max(h, *next.first); if(h-l<ret[1]-ret[0]) {ret[0] = l; ret[1] = h;} } return ret; } };