leetcode

commit 897de71ae7774fef9e5ea0f037ffd4aa0ceb382f
parent 4519fb1fb5218a3b9ee91819dc3475b3828c73b9
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 13 Oct 2024 22:23:28 +0200

Daily Problem

Diffstat:
A
Problems/0632.cpp
 | 
28
++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 29 insertions(+), 0 deletions(-)
diff --git a/Problems/0632.cpp b/Problems/0632.cpp
@@ -0,0 +1,28 @@
+class Solution {
+  public:
+    vector<int> smallestRange(const vector<vector<int>> &nums) const {
+        using ti = tuple<int, int, int>;
+        priority_queue<ti, vector<ti>, greater<ti>> pq;
+        int maxi = -1;
+
+        for (int i = 0; i < size(nums); i++) {
+            pq.emplace(nums[i][0], i, 0);
+            maxi = max(maxi, nums[i][0]);
+        }
+
+        vector<int> res = {0, INT_MAX};
+        while (!pq.empty()) {
+            const auto [mini, list, elem] = pq.top();
+            pq.pop();
+
+            if (maxi - mini < res[1] - res[0]) res = {mini, maxi};
+            if (elem + 1 == size(nums[list])) break;
+
+            const int next = nums[list][elem + 1];
+            pq.emplace(next, list, elem + 1);
+            maxi = max(maxi, next);
+        }
+
+        return res;
+    }
+};
diff --git a/README.md b/README.md
@@ -439,6 +439,7 @@ for solving problems.
 |  0626  |   Medium   | [Exchange Seats](Problems/0626.cpp)                                                                |
 |  0627  |    Easy    | [Swap Salary](Problems/0627.cpp)                                                                   |
 |  0629  |    Hard    | [K Inverse Pairs Array](Problems/0629.cpp)                                                         |
+|  0632  |    Hard    | [Smallest Range Covering Elements from K Lists](Problems/0632.cpp)                                 |
 |  0633  |   Medium   | [Sum of Square Numbers](Problems/0633.cpp)                                                         |
 |  0636  |   Medium   | [Exclusive Time of Functions](Problems/0636.cpp)                                                   |
 |  0637  |    Easy    | [Average of Levels in Binary Tree](Problems/0637.cpp)                                              |