Given n appointments, find all conflicting appointments

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;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro