Given N Appointments, find all Conflicting Appointments

Approach #1

🧑‍💻 A very simple or naive solution would be to compare each appointment with every other appointment to check whether they conflict or not.

Pseudocode

PRINT_CONFLICTING (appointments):
    for i = 0 till i < appointments.size - 1:
        for j = i+1 till j < appointments.size:
            if appointment[i] is conflicting with appointment[j]:
                print conflict within appointments
            end if
        end for
    end for

Implementation in C++ 

#include <bits/stdc++.h>
using namespace std;


// function to print appointment
void print(pair<int, int> appointment)
{
    cout << "[" << appointment.first << " " << appointment.second << "]";
}


// function to check whether two appointments conflict or not
bool isConflicting(pair<int, int> a1, pair<int, int> a2)
{
    if(a1.first < a2.second && a2.first < a1.second) return true;


    // appointments are not conflicting
    return false;
}



// function to print the conflicting appointments
void printConflicting(vector<pair<int, int>> appointments)
{


    // we are basically selecting one appointment and then comparing it
    // with all the other available appointments whether they conflict or not
    for (int i = 0; i < appointments.size() - 1; i++)
    {
        for (int j = i + 1; j < appointments.size(); j++)
        {
            if (isConflicting(appointments[i], appointments[j]))
            {
                print(appointments[j]);
                cout << "\tconflicting with\t";
                print(appointments[i]);
                cout << '\n';
            }
        }
    }
}


int main()
{
    // list of appointments
    vector<pair<int, int>> appointments = {{1, 5}, {5, 8}, {4, 5}, {6, 10}, {10, 30}};


    // printing conflicting appointments
    printConflicting(appointments);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

[4 5]   conflicting with        [1 5]
[6 10]  conflicting with        [5 8]

Time Complexity

We are traversing the appointment list and while traversing we are again traversing to check whether the appointments conflict or not. So, the time taken by our program O(N^2)⏱️.

Space Complexity

Constant space is used in the implementation of the approach. So, the space complexity of our program is O(1) 📝.

Approach #2

🧑‍💻 We can use the interval tree to solve the above problem. We can do the following first: create an interval tree with the very first appointment after that before inserting any other appointment into the interval tree. 

✨ Check whether the appointment conflicts with any other appointment available in the interval tree or not.

Algorithm

1. ⭐ Create an interval tree using the first appointment available in the list.
    
2. ⭐ From the second appointment onwards before inserting it in the tree check whether it conflicts with any other appointment available in the interval tree or not.

Implementation in C++ 

#include <bits/stdc++.h>
using namespace std;

struct Appointment
{
    int startTime;
    int endTime;
};

// node for interval tree
class Node
{
public:
    // represents start time and end time
    Appointment *ap;
    int max;
    Node *left, *right;

    Node(Appointment a)
    {
        ap = new Appointment(a);
        max = a.endTime;
        left = right = nullptr;
    }
};

// function to insert new Node into interval tree
Node *insert(Node *root, Appointment a)
{
    if (!root)
        return new Node(a);

    // getting start time of root node
    int st = root->ap->startTime;

    // if root's start time is smaller the current appointment goes to left subtree
    if (a.startTime < st)
        root->left = insert(root->left, a);

    // else the current appointment goes to right subtree
    else
        root->right = insert(root->right, a);

    // updating the max value
    if (root->max < a.endTime)
        root->max = a.endTime;

    return root;
}

// function to check whether two appointments conflict or not
bool isConflicting(Appointment a1, Appointment a2)
{
    // appointments are conflicting
    if (a1.startTime < a2.endTime && a2.startTime < a1.endTime)
        return true;

    // appointments are not conflicting
    return false;
}

// searching for conflicting appointments
Appointment *searchAppointments(Node *root, Appointment ap)
{
    if (!root)
        return nullptr;

    // given appointment is conflicting
    if (isConflicting(ap, *root->ap))
        return root->ap;

    if (root->left && root->left->max >= ap.startTime)
        return searchAppointments(root->left, ap);

    return searchAppointments(root->right, ap);
}

// function to print the conflicting appointments
void printConflicting(vector<Appointment> appointments)
{
    // creating interval tree with first appointment
    Node *root = nullptr;
    root = insert(root, appointments[0]);

    // iterating rest of the appointments
    for (int i = 1; i < appointments.size(); i++)
    {

        // checking if the current appointment conflicts with any other appointment
        Appointment *ap = searchAppointments(root, appointments[i]);
        if (ap)
        {
            cout << "[" << appointments[i].startTime << " " << appointments[i].endTime << "]\t";
            cout << "conflicts with\t";
            cout << "[" << ap->startTime << " " << ap->endTime << "]\n";
        }

        // inserting the current appointment into the interval tree
        root = insert(root, appointments[i]);
    }
}

// main function
int main()
{
    // list of appointments
    vector<Appointment> appointments = {{1, 5}, {5, 8}, {4, 5}, {6, 10}, {10, 30}};

    // printing conflicting appointments
    printConflicting(appointments);

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

[4 5] conflicts with [1 5]
[6 10] conflicts with [5 8]

Time Complexity

 Inserting a node in a BST takes O(H) time, where H is the height of the tree. Here, H can go up to N where N is the number of nodes in the tree since we are not using balanced BSTs.

The overall time complexity of the program is greater than O(N * H) where N is the number of appointments and H is the height of the BST. If we use AVL or RBT as the BST then the complexity will be O(N * LogN) ⏱️.

Space Complexity

We are creating an interval tree of N nodes. So, the extra space used by our program is O(N), where N is the number of nodes 📝.

Check out this problem - Duplicate Subtree In Binary Tree

Frequently Asked Questions

What is a segment tree?

In general, a segment tree is a binary tree that is used to store intervals or segments. The Segment Tree's nodes each represent an interval. 

What is a binary search tree?

A Binary search tree is a type of binary tree in which all the nodes having lesser values than the root node are kept on the left subtree, and similarly, the values greater than the root node are kept on the right subtree.

How much time does inserting an element take in BST?

In general, inserting an element in BST takes O(h) time, where h is the height of BST But if the tree is skewed then the time complexity of insertion would be O(N), where N is the number of nodes in BST.

Conclusion 

This article has shown you two different approaches to solve the problem in which we will be given a list of appointments and we have to find all of the conflicting appointments.

If you think this blog has helped you enhance your knowledge about the above question, and if you would like to learn more, check out our articles 
 

• Balanced Binary Search Trees 😁
   
• Binary search tree 😎
   
• BST into a Min-Heap Without Using Array
   
• Count the number of magical Indices in an array
   

and many more on our Website. 

Grow your knowledge by enrolling in the courses provided by us. You can also participate in mock tests, and interview puzzles and can solve problems available on our website. In case you are preparing for the interview have a look at interview experiences and an interview bundle for placement preparations.
 Please upvote our blog 🏆 if you find them useful to help other ninjas grow

Happy Learning!