Leetcode 632: Smallest Range Covering Elements from K Lists

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. -10^5 <= value of elements <= 10^5.

Problem Analysis:

Obviously we can collect the first elements of k lists to get a valid range, which contains one element of each lists.

Every time we extract the minimum element of the range, suppose the element is from ith list, then we add the next element of the ith list into the range, the new range is also a valid range. Until matched the end of the ith list.

Finally we iterate all valid ranges to find out the smallest one.

Solution:

class Solution {
public:
  vector<int> smallestRange(vector<vector<int>>& nums) {
    typedef vector<int>::iterator vi;
    typedef vector<pair<vi, vi>> vp;
    auto my_comp = [](const pair<vi, vi>& lhs, const pair<vi, vi>& rhs) {
      return *lhs.first > *rhs.first; };
    priority_queue<pair<vi, vi>, vp, decltype(my_comp)> pq(my_comp);
    vector<int> res(2, numeric_limits<int>::min());
    for (auto& array: nums) {
      pq.push(make_pair(array.begin(), array.end()));
      res[1] = max(res[1], *array.begin());
    }
    res[0] = *pq.top().first;
    vector<int> current{res};
    while (!pq.empty()) {
      auto its = pq.top();
      ++its.first;
      pq.pop();
      if (its.first == its.second) break;
      current[1] = max(current[1], *its.first);
      pq.push(its);
      current[0] = *pq.top().first;
      if (current[1] - current[0] < res[1] - res[0])
        res = current;
    }
    return res;
  }
};

Time Complexity: O(n)

Space Complexity: O(1)