leetcode

commit 4d3e1fb637c5d4393166c54b2abcd30521d4c61e
parent 6b97a182ad0c8a154b8d9635927778ce6cf328c7
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Sun, 12 Mar 2023 20:14:23 +0100

Daily Problem

Diffstat:
M
Problems/0023.cpp
 | 
26
++++++++++++++++++++++++++

1 file changed, 26 insertions(+), 0 deletions(-)
diff --git a/Problems/0023.cpp b/Problems/0023.cpp
@@ -1,3 +1,4 @@
+// Naive solution, barely passed
 class Solution {
 public:
   ListNode *mergeKLists(vector<ListNode *> &lists) {
@@ -20,3 +21,28 @@ public:
     return dummy->next;
   }
 };
+
+// Proper solution
+class Solution {
+  typedef pair<int, int> pii;
+
+public:
+  ListNode *mergeKLists(vector<ListNode *> &lists) {
+    ListNode *dummy, *tmp;
+    tmp = dummy = new ListNode;
+
+    auto cmp = [](const pii &a, const pii &b) { return a.first > b.first; };
+    priority_queue<pii, vector<pii>, decltype(cmp)> pq(cmp);
+    for (int i = 0; i < lists.size(); i++)
+      if (lists[i]) pq.push({lists[i]->val, i});
+    while (!pq.empty()) {
+      int index = pq.top().second;
+      pq.pop();
+      ListNode *t = lists[index];
+      lists[index] = lists[index]->next;
+      if (lists[index]) pq.push({lists[index]->val, index});
+      tmp = tmp->next = t;
+    }
+    return dummy->next;
+  }
+};