Friday, May 15, 2015

Merge overlapping Interval

Problem: Given a set of intervals, not necessarily in sorted order, merge all overlapping intervals into one.

Solution:
  1. Sort all intervals according to their start time.
  2. Push first one into a stack.
  3. For each interval check if current interval overlaps with top of the stack; if no, then push it onto the stack else if its end time is more than top end time then change the end time of top with current interval's end time.
  4. At the end stack will have the merged intervals.

Implementation:


struct Interval
{
 int start;
 int end;
};

bool compareInterval(Interval i1, Interval i2)
{
 return i1.start < i2.start ? true : false;

}

void mergeInterval(Interval* intervals, int len)
{
if(intervals == 0 || len <= 0)
return;

std::sort(intervals, intervals + len, compareInterval);
std::stack<Interval> stInterval;
stInterval.push(intervals[0]);

for(int i = 1; i < len; ++i) 
{
Interval tempInterval = stInterval.top();
if(tempInterval.end < intervals[i].start)
stInterval.push(intervals[i]);
else if(tempInterval.end < intervals[i].end)
{
tempInterval.end = intervals[i].end;
stInterval.pop();
stInterval.push(tempInterval);
}
}

std::cout<<"Merged Intervals:\n";
    while (!stInterval.empty())
    {
        Interval interval = stInterval.top();
        std::cout <<'['<<interval.start<<", "<< interval.end<<']'<<'\t';
stInterval.pop();
    }

} 

Complexity: O(nlogn)


No comments:

Post a Comment