Problem

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].

Analysis

If End element of an interval is greater than start element of next element, then merge those two intervals and make it as one interval.

Javascript Code

var Interval = function (s, e) {
    this.start = s;
    this.end = e;
}
 
function merge(intervals) {
 
        if (intervals == null || intervals.length <= 1)
            return intervals;
 
        // sort intervals by using self-defined Comparator
        intervals.sort(function(a,b) {
                if(a.start > b.start) {
                    return 1;
                } else if(a.start < b.start) {
                    return -1;
                } 
                    return 0;
            });
 
        var result = [];
 
        var prev = intervals[0];
        for (var i = 1; i < intervals.length; i++) {
            var curr = intervals[i];
 
            if (prev.end >= curr.start) {
                // merged case
                var merged = new Interval(prev.start, Math.max(prev.end, curr.end));
                prev = merged;
            } else {
                result.push(prev);
                prev = curr;
            }
        }
 
        result.push(prev);
 
        return result;
}

var intevs = [new Interval(1,3), new Interval(5,10), new Interval(9,15)];

0 comments:

Blogroll

Follow this blog by Email

Popular Posts