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;
}

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

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…:slight_smile:

//