1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Approach #1
3.1.
Pseudocode
3.2.
Implementation in C++
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Approach #2
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Time Complexity
4.2.2.
Space Complexity
5.
5.1.
What is a segment tree?
5.2.
What is a binary search tree?
5.3.
How much time does inserting an element take in BST?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Given N Appointments, find all Conflicting Appointments

Harsh
0 upvote

## Introduction

Data structures and algorithms are one of the most important topics if you are preparing for an interview. Having a proper understanding of data structures requires you to solve many problems.

In this blog, we are going to discuss a coding problem in which we have to find all the conflicting appointments from the list of given appointments.

## Problem Statement

You will be given a list of appointments, where a single appointment contains the start time and end time. Your task is to find all of the conflicting appointments.

An appointment is conflicting when there is another appointment between the start and end time of the current appointment.

### Sample Examples

Input

Output

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

Explanation

⭐ As we can see from the above figure appointment1 and appointment2 are conflicting. The same goes for the appointment [6 10] and [5 8].

## 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;
}``````

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;
}``````

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

### 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

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!

Live masterclass