(Merge k Sorted Lists)

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Thoughts:
We start with the first list and then merge it with the second list, then the third list, so on and the so forth. For merging two sorted linked list, we use the linear merging algorithm borrowed from Merge Sort. The total complexity is O(kn).

Code (Java):

public class Solution {
	public ListNode mergeKLists(ArrayList<ListNode> lists) {
		ListNode head = null;
		for (ListNode node : lists)
			head = mergeTwoLists(head, node);
		return head;
	}

	private ListNode mergeTwoLists(ListNode head1, ListNode head2) {
		if (head1 == null || head2 == null)
			return head1 == null ? head2 : head1;

		if (head1.val < head2.val) {
			head1.next = mergeTwoLists(head1.next, head2);
			return head1;
		} else {
			head2.next = mergeTwoLists(head2.next, head1);
			return head2;
		}
	}
}

Code (C++):

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        ListNode *head = NULL;
    	for(int i = 0; i < lists.size(); ++i)
			head = mergeTwoLists(head, lists[i]);
		return head;
    }

private: 
    ListNode *mergeTwoLists(ListNode *head1, ListNode *head2) {
		if (head1 == NULL || head2 == NULL)
			return head1 == NULL ? head2 : head1;

        if (head1 -> val < head2 -> val) {
			head1 -> next = mergeTwoLists(head1 -> next, head2);
            return head1;
		} else {
			head2 -> next = mergeTwoLists(head2 -> next, head1);
            return head2;
		}
	}
};

(Merge Intervals)

Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Thoughts:
We first sort the list according to the start-time. Then for any interval i in the middle, it has overlap with the next interval j iff j.start <= i.end. If so, we know we are about to merge them into a new interval k. And k.start = i.start && k.end = \max(i.end, j.end).

Code (Java):

public class Solution {
    public class MyComparator implements Comparator{
        public int compare(Object o1, Object o2) {
            Interval i1 = (Interval)o1;
            Interval i2 = (Interval)o2;
            return i1.start - i2.start;
        }
    }
    
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        if(intervals == null)
            return null;
        ArrayList<Interval> result = new ArrayList<Interval>();
        if(intervals.size() == 0)
            return result;
        if(intervals.size() == 1) {
            result.addAll(intervals);
            return result;
        }
        Collections.sort(intervals, new MyComparator());
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i = 1; i < intervals.size(); ++i) {
            Interval curr = intervals.get(i);
            if(curr.start <= end) {
                end = Math.max(end, curr.end);
            } else {
                result.add(new Interval(start, end));
                start = curr.start;
                end = curr.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}

Code (C++):
Thanks to this post:

class Solution {
class Solution {
public:
    struct MyComparatorClass {
        bool operator() (Interval i, Interval j) { return (i.start < j.start);}
    } myComparator;

    vector<Interval> merge(vector<Interval> &intervals) {
        vector<Interval> result;
        if(intervals.size() == 0)
            return result;
        if(intervals.size() == 1) {
            result.push_back(intervals[0]);
            return result;
        }
        sort(intervals.begin(), intervals.end(), myComparator);
        vector<Interval>::iterator it = intervals.begin();
        Interval current = *(it)++;
        while (it != intervals.end()){
            if (current.end >= it -> start) {
                current.end = std::max(current.end, it -> end); 
            } else {
                result.push_back(current);
                current = *(it);
            }
            it++;
        }
        result.push_back(current);
        return result;
    }
};