QUESTION

Given n appointments, find all conflicting appointments.\n\nExamples:\n\nInput: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}\nOutput: Following are conflicting intervals\n[3,7] Conflicts with [1,5]\n[2,6] Conflicts with [1,5]\n[5,6] Conflicts with [3,7]\n[4,100] Conflicts with [1,5]\nAn appointment is conflicting, if it conflicts with any of the previous appointment.

ANSWER

#include <iostream>
using namespace std;
struct Interval
{
    int low, high;
};
struct ITNode
{
    Interval *i;  
    int max;
    ITNode *left, *right;
};
ITNode * newNode(Interval i)
{
    ITNode *temp = new ITNode;
    temp->i = new Interval(i);
    temp->max = i.high;
    temp->left = temp->right = NULL;
};
ITNode *insert(ITNode *root, Interval i)
{
    if (root == NULL)
        return newNode(i);
    int l = root->i->low;
    if (i.low < l)
        root->left = insert(root->left, i);
    else
        root->right = insert(root->right, i);
    if (root->max < i.high)
        root->max = i.high;
 
    return root;
}
bool doOVerlap(Interval i1, Interval i2)
{
    if (i1.low < i2.high && i2.low < i1.high)
        return true;
    return false;
}
Interval *overlapSearch(ITNode *root, Interval i)
{
    if (root == NULL) return NULL;
    if (doOVerlap(*(root->i), i))
        return root->i;
    if (root->left != NULL && root->left->max >= i.low)
        return overlapSearch(root->left, i);
    return overlapSearch(root->right, i);
}
void printConflicting(Interval appt[], int n)
{
     ITNode *root = NULL;
     root = insert(root, appt[0]);
     for (int i=1; i<n; i++)
     {
         Interval *res = overlapSearch(root, appt[i]);
         if (res != NULL)
            cout << "[" << appt[i].low << "," << appt[i].high
                 << "] Conflicts with [" << res->low << ","
                 << res->high << "]\n";
         root = insert(root, appt[i]);
     }
}
 
int main()
{
    Interval appt[] = { {1, 5}, {3, 7}, {2, 6}, {10, 15},
                        {5, 6}, {4, 100}};
    int n = sizeof(appt)/sizeof(appt[0]);
    cout << "Following are conflicting intervals\n";
    printConflicting(appt, n);
    return 0;
}