OverlappingIntervals

/*
    The C++ program joins overlapping intervals
    Uses Merge Sort
    Sample invervals: (8, 9);  (3, 4); (2, 5); (1, 2); (6, 7)
    Answer: (1, 5); (6, 7); (8, 9)
    Requirement: start < end, i.e. (6, 5) is not valid interval
*/
#include <iostream>
using namespace std;

const int n = 5;

struct interval {
    int start;
    int end;
    bool flag;
};

bool overlap(interval a, interval b);
interval join(interval a, interval b);
void mergesort(interval *a, int low, int high);
void merge(interval *a, int low, int high, int mid);

int main() {

    unsigned i, j;

    interval x[n] =
    {
        {8, 9},
        {3, 4},
        {2, 5},
        {1, 2},
        {6, 7}
    };

    for (i=0; i<n; i++) x[i].flag = 1; //Initial values

    mergesort(x,0,n-1);

    cout << "Sorted intervals:\n";
    for (i=0; i<n; i++) {
        cout << x[i].start << ' ' << x[i].end << '\n';
    }

    int k = 0;
    for (i=0; i<n-1; i++) {
        if (x[i].flag) {
            for (j=i+1; j<n; j++) {
                if (overlap(x[i], x[j])) {
                    x[i] = join(x[i], x[j]);
                    x[j].flag = 0;  // This interval is joined to an overlapping interval
                }
            }
        }

    }
    cout << "Joined intervals:\n";
    for (i=0; i<n; i++) {
        if (x[i].flag) {
            cout << x[i].start << ' ' << x[i].end << '\n';
        }
    }

    return 0;
}

bool overlap(interval a, interval b) {
    return ((a.start <= b.end)&&(a.end >= b.start)) ? 1 : 0;
}

interval join(interval a, interval b) {
    interval c;

    c.start = (a.start < b.start) ? a.start : b.start;
    c.end = (a.end > b.end) ? a.end : b.end;
    c.flag = 1;

    return c;
}

void mergesort(interval *a, int low, int high) {
    int mid;
    if (low < high)
    {
        mid=(low+high)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        merge(a,low,high,mid);
    }
    return;
}

void merge(interval *a, int low, int high, int mid)
{
    int i, j, k;
    interval c[n];
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high)
    {
        if (a[i].start == a[j].start)
        {
            if (a[i].end < a[j].end) {
                c[k] = a[i];
                k++;
                i++;
            } else {
                c[k] = a[j];
                k++;
                j++;
            }
        } else if (a[i].start < a[j].start) {
            c[k] = a[i];
            k++;
            i++;
        } else {
            c[k] = a[j];
            k++;
            j++;
        }

    }
    while (i <= mid)
    {
        c[k] = a[i];
        k++;
        i++;
    }
    while (j <= high)
    {
        c[k] = a[j];
        k++;
        j++;
    }
    for (i = low; i < k; i++)
    {
        a[i] = c[i];

    }

}