Merge K Sorted Arrays

• Lintcode : 486 / Leetcode 23(Similar)
• Level : Medium

Problem

Given k sorted integer arrays, merge them into one sorted array.

Example
Example 1:

Input: 
  [
    [1, 3, 5, 7],
    [2, 4, 6],
    [0, 8, 9, 10, 11]
  ]
Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Example 2:

Input:
  [
    [1,2,3],
    [1,2]
  ]
Output: [1,1,2,2,3]
Challenge
Do it in O(N log k).

N is the total number of integers.
k is the number of arrays.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(nlogm) (m rows, n columns)
space: O(n * m)

Answer

class Node {
public:
    int r, c, val;
    Node (int _r, int _c, int _val) : r(_r), c(_c), val(_val) {}
};
struct cmp {
    bool operator() (const Node &a, const Node &b) {
        return a.val > b.val;
    }
};
class Solution {
public:
    vector<int> mergekSortedArrays(vector<vector<int>> &arrays) {
        priority_queue<Node, vector<Node>, cmp> pq;
        for (int i = 0; i < arrays.size(); i++) {
            if (arrays[i].empty()) continue;
            pq.push(Node(i, 0, arrays[i][0]));
        }
        vector<int> ans;
        while (!pq.empty()) {
            Node n = pq.top(); pq.pop();
            ans.push_back(n.val);
            if (n.c + 1 < arrays[n.r].size()) pq.push(Node(n.r, n.c + 1, arrays[n.r][n.c + 1]));
        }
        return ans;
    }
};

tags: heap

​

Merge K Sorted Interval Lists

• Lintcode : 577 / Leetcode : 23 (Similar)
• Level : Medium

Problem

Merge K sorted interval lists into one sorted interval list. You need to merge overlapping intervals too.

Example
Example1

Input: [
  [(1,3),(4,7),(6,8)],
  [(1,2),(9,10)]
]
Output: [(1,3),(4,8),(9,10)]
Example2

Input: [
  [(1,2),(5,6)],
  [(3,4),(7,8)]
]
Output: [(1,2),(3,4),(5,6),(7,8)]

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(nlogm) (m rows, n column)
space: O(n * m)

Answer

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

class Node {
public:
    int r, c;
    Interval i;
    Node (int _r, int _c, Interval _i) : r(_r), c(_c), i(_i) {}

};

struct cmp {
    bool operator() (const Node &a, const Node &b) {
        if (a.i.start == b.i.start) return a.i.end > b.i.end;
        return a.i.start > b.i.start;
    }
};
class Solution {
public:
    vector<Interval> mergeKSortedIntervalLists(vector<vector<Interval>> &intervals) {
        priority_queue<Node, vector<Node>, cmp> pq;
        for (int i = 0; i < intervals.size(); i++) {
            if (!intervals[i].empty()) {
                pq.push(Node(i, 0, intervals[i][0]));
            }
        }
        vector<Interval> ans;
        while (!pq.empty()) {
            Node n = pq.top(); pq.pop();
            if (!ans.empty() && ans[ans.size() - 1].end >= n.i.start) {
                ans[ans.size() - 1].end = max(n.i.end, ans[ans.size() - 1].end);
            }else {
                ans.push_back(n.i);
            }
            if (n.c + 1 < intervals[n.r].size()) pq.push(Node(n.r, n.c + 1, intervals[n.r][n.c + 1]));
        }
        return ans;
    }
};

tags: heap

​