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!!!