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

​