Checking whether given intervals are contiguous or not

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s