(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;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: