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

Solution: Sorting

If we sort the intervals by their start value, then each set of intervals that can be merged will appear as a contiguou run in the sorted list.

  1. We sort the list as described.
  2. We insert the first interval into our merged list and continue considering each interval in turn as follows

    a. If the current interval begins after the previous interval ends, then they do not overlap and we can append the current interval to merged. b. Otherwise, they do overlap, and we merge them by updating the end of the previous interval if it is less than the end of the current interval.

bool myCompare(Interval a, Interval b) { 
    return a.start < b.start; 
}

vector<Interval> merge(vector<Interval>& intervals) {        
    sort(intervals.begin(), intervals.end(), myCompare);

    vector<Interval> result;
    for(int i=0; i<intervals.size(); i++) {
        if(result.empty() || result.back().end < intervals[i].start) {
            result.push_back(intervals[i]);
        } else {
            result.back().end = max(result.back().end, intervals[i].end);
        }
    }
    return result;
}

results matching ""

    No results matching ""