Problem: Link
u will be given pairs.. u need to see whether they have any gaps..
ex1: max no:20
pairs: 11-15, 0-5, 18-20, 14-19, 6-13
u can think pairs are like intervals..the above has no gaps..
because 0-5,6-13,11-15,18-20 have all numbers from 0 (min) to 20(max)
ex2: 11-15, 0-5, 18-20, 14-16, 6-13
this have gap as the intervals miss a number from 0 to 20 i.e.,17
Solution:

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
int minimum, maximum;
}Interval;
/* Compares intervals based on minimum element */
int cmpInterval(const void *a, const void *b)
{
return ((Interval *)a)->minimum - ((Interval *)b)->minimum;
}
int isIntervalsContiguous(Interval intervals[], int n)
{
/* Sort the intervals */
qsort(intervals, n, sizeof(Interval), cmpInterval);
/* Check whether they are contiguous */
int i;
for(i = 1; i < n; i++)
{
if(intervals[i].minimum > intervals[i - 1].maximum + 1)
return 0;
}
return 1;
}
int main()
{
int n;
scanf("%d", &n);
Interval intervals[n];
int i;
for(i = 0; i < n; ++i)
scanf("%d%d", &intervals[i].minimum, &intervals[i].maximum);
printf("isContiguous: %d\n", isIntervalsContiguous(intervals, n));
}

### Like this:

Like Loading...

*Related*