# Merge Sets

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

Write it in ANSI C

tHIS IS WHAT i TRIED, BUT IT HAS MANY FLAWS. Majorly that [2,3] will be omitted if [1,5] is present. But[2,4] and [3,6] will not show [2,6]

``````#include<stdio.h>
int main()
{
char q;
int a[20],b[20],c[20],d[20],i,j,k;
for(i=0;i<20;i++)
{
puts("enter lower limit of interval");
scanf("%d",&a[i]);
puts("enter upper limit of interval");
scanf("%d",&b[i]);
}

for(k=0;k<i;k++)
{
for(j=0;j<20;j++)
{
if((a[j]>a[k])|(b[j]<b[k]))
{
c[i]=a[j];
d[i]=b[j];
}
}
}
for(k=0;k<i;k++)
{
printf("%d %d \n",c[k],d[k]);
}
return 0;
}``````

I will not be writing the whole code…but can help you out with the basic logic…

considering the example that you have given in the ques…

``````[1,3] [2,6] [8,10] [15,18]
``````

Mark all the numbers as start or end of the set, put all of them in the same array and sort them in ascending order.

``````1-0 3-1
2-0 6-1
8-0 10-1
15-0 18-1
``````

where 0 indicates start and 1 indicates end!!!

upon sorting you will get the following sequence…

``````1-0 2-0 3-1 6-1 8-0 10-1 15-0 18-1
``````

now what you can do is traverse the array and keep a temporary counter(which is intialized to 0) and whenever you encounter a ‘0’ increment the counter and whenever you encounter a ‘1’ decrement it…whenever the counter becomes 0 it indicates that all sets till now have merged…

``````element    counter
1-0       1
2-0       2
3-1       1
6-1       0    //first set having start 1 and end 6
8-0       1
10-1      0    //second set having start 8 and end 10
15-0      1
18-1      0    //third set having start 15 and end 18
``````

hope this helps…

what have u tried yet…no1s going to do ur home work here…put some effort…write a code…then ask!!!