Given n appointments, find all conflicting appointments.
Examples:
Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}
Output: Following are conflicting intervals
[3,7] Conflicts with [1,5]
[2,6] Conflicts with [1,5]
[5,6] Conflicts with [3,7]
[4,100] Conflicts with [1,5]
An appointment is conflicting, if it conflicts with any of the previous appointments in array.
[ad type=”banner”]A Simple Solution is to one by one process all appointments from second appointment to last. For every appointment i, check if it conflicts with i-1, i-2, … 0. The time complexity of this method is O(n2).
We can use Interval Tree to solve this problem in O(nLogn) time. Following is detailed algorithm.
1) Create an Interval Tree, initially with the first appointment.
2) Do following for all other appointments starting from the second one.
a) Check if the current appointment conflicts with any of the existing
appointments in Interval Tree. If conflicts, then print the current
appointment. This step can be done O(Logn) time.
b) Insert the current appointment in Interval Tree. This step also can
be done O(Logn) time.
Following is C++ implementation of above idea.
[pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20print%20all%20conflicting%20appointments%20in%20a%0A%2F%2F%20given%20set%20of%20appointments%0A%23include%20%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Structure%20to%20represent%20an%20interval%0Astruct%20Interval%0A%7B%0A%20%20%20%20int%20low%2C%20high%3B%0A%7D%3B%0A%20%0A%2F%2F%20Structure%20to%20represent%20a%20node%20in%20Interval%20Search%20Tree%0Astruct%20ITNode%0A%7B%0A%20%20%20%20Interval%20*i%3B%20%20%2F%2F%20’i’%20could%20also%20be%20a%20normal%20variable%0A%20%20%20%20int%20max%3B%0A%20%20%20%20ITNode%20*left%2C%20*right%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20create%20a%20new%20Interval%20Search%20Tree%20Node%0AITNode%20*%20newNode(Interval%20i)%0A%7B%0A%20%20%20%20ITNode%20*temp%20%3D%20new%20ITNode%3B%0A%20%20%20%20temp-%3Ei%20%3D%20new%20Interval(i)%3B%0A%20%20%20%20temp-%3Emax%20%3D%20i.high%3B%0A%20%20%20%20temp-%3Eleft%20%3D%20temp-%3Eright%20%3D%20NULL%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20utility%20function%20to%20insert%20a%20new%20Interval%20Search%20Tree%0A%2F%2F%20Node.%20This%20is%20similar%20to%20BST%20Insert.%20%20Here%20the%20low%20value%0A%2F%2F%20%20of%20interval%20is%20used%20tomaintain%20BST%20property%0AITNode%20*insert(ITNode%20*root%2C%20Interval%20i)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20case%3A%20Tree%20is%20empty%2C%20new%20node%20becomes%20root%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%0A%20%20%20%20%20%20%20%20return%20newNode(i)%3B%0A%20%0A%20%20%20%20%2F%2F%20Get%20low%20value%20of%20interval%20at%20root%0A%20%20%20%20int%20l%20%3D%20root-%3Ei-%3Elow%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20root’s%20low%20value%20is%20smaller%2C%20then%20new%20interval%0A%20%20%20%20%2F%2F%20%20goes%20to%20left%20subtree%0A%20%20%20%20if%20(i.low%20%3C%20l)%0A%20%20%20%20%20%20%20%20root-%3Eleft%20%3D%20insert(root-%3Eleft%2C%20i)%3B%0A%20%0A%20%20%20%20%2F%2F%20Else%2C%20new%20node%20goes%20to%20right%20subtree.%0A%20%20%20%20else%0A%20%20%20%20%20%20%20%20root-%3Eright%20%3D%20insert(root-%3Eright%2C%20i)%3B%0A%20%0A%20%20%20%20%2F%2F%20Update%20the%20max%20value%20of%20this%20ancestor%20if%20needed%0A%20%20%20%20if%20(root-%3Emax%20%3C%20i.high)%0A%20%20%20%20%20%20%20%20root-%3Emax%20%3D%20i.high%3B%0A%20%0A%20%20%20%20return%20root%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20check%20if%20given%20two%20intervals%20overlap%0Abool%20doOVerlap(Interval%20i1%2C%20Interval%20i2)%0A%7B%0A%20%20%20%20if%20(i1.low%20%3C%20i2.high%20%26%26%20i2.low%20%3C%20i1.high)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20return%20false%3B%0A%7D%0A%20%0A%2F%2F%20The%20main%20function%20that%20searches%20a%20given%20interval%20i%0A%2F%2F%20in%20a%20given%20Interval%20Tree.%0AInterval%20*overlapSearch(ITNode%20*root%2C%20Interval%20i)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20Case%2C%20tree%20is%20empty%0A%20%20%20%20if%20(root%20%3D%3D%20NULL)%20return%20NULL%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20given%20interval%20overlaps%20with%20root%0A%20%20%20%20if%20(doOVerlap(*(root-%3Ei)%2C%20i))%0A%20%20%20%20%20%20%20%20return%20root-%3Ei%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20left%20child%20of%20root%20is%20present%20and%20max%20of%20left%20child%0A%20%20%20%20%2F%2F%20is%20greater%20than%20or%20equal%20to%20given%20interval%2C%20then%20i%20may%0A%20%20%20%20%2F%2F%20overlap%20with%20an%20interval%20is%20left%20subtree%0A%20%20%20%20if%20(root-%3Eleft%20!%3D%20NULL%20%26%26%20root-%3Eleft-%3Emax%20%3E%3D%20i.low)%0A%20%20%20%20%20%20%20%20return%20overlapSearch(root-%3Eleft%2C%20i)%3B%0A%20%0A%20%20%20%20%2F%2F%20Else%20interval%20can%20only%20overlap%20with%20right%20subtree%0A%20%20%20%20return%20overlapSearch(root-%3Eright%2C%20i)%3B%0A%7D%0A%20%0A%2F%2F%20This%20function%20prints%20all%20conflicting%20appointments%20in%20a%20given%0A%2F%2F%20array%20of%20apointments.%0Avoid%20printConflicting(Interval%20appt%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%20%2F%2F%20Create%20an%20empty%20Interval%20Search%20Tree%2C%20add%20first%0A%20%20%20%20%20%2F%2F%20appointment%0A%20%20%20%20%20ITNode%20*root%20%3D%20NULL%3B%0A%20%20%20%20%20root%20%3D%20insert(root%2C%20appt%5B0%5D)%3B%0A%20%0A%20%20%20%20%20%2F%2F%20Process%20rest%20of%20the%20intervals%0A%20%20%20%20%20for%20(int%20i%3D1%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%2F%2F%20If%20current%20appointment%20conflicts%20with%20any%20of%20the%0A%20%20%20%20%20%20%20%20%20%2F%2F%20existing%20intervals%2C%20print%20it%0A%20%20%20%20%20%20%20%20%20Interval%20*res%20%3D%20overlapSearch(root%2C%20appt%5Bi%5D)%3B%0A%20%20%20%20%20%20%20%20%20if%20(res%20!%3D%20NULL)%0A%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22%5B%22%20%3C%3C%20appt%5Bi%5D.low%20%3C%3C%20%22%2C%22%20%3C%3C%20appt%5Bi%5D.high%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20%22%5D%20Conflicts%20with%20%5B%22%20%3C%3C%20res-%3Elow%20%3C%3C%20%22%2C%22%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%3C%3C%20res-%3Ehigh%20%3C%3C%20%22%5D%5Cn%22%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%2F%2F%20Insert%20this%20appointment%0A%20%20%20%20%20%20%20%20%20root%20%3D%20insert(root%2C%20appt%5Bi%5D)%3B%0A%20%20%20%20%20%7D%0A%7D%0A%20%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20create%20interval%20tree%20shown%20in%20above%20figure%0A%20%20%20%20Interval%20appt%5B%5D%20%3D%20%7B%20%7B1%2C%205%7D%2C%20%7B3%2C%207%7D%2C%20%7B2%2C%206%7D%2C%20%7B10%2C%2015%7D%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B5%2C%206%7D%2C%20%7B4%2C%20100%7D%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(appt)%2Fsizeof(appt%5B0%5D)%3B%0A%20%20%20%20cout%20%3C%3C%20%22Following%20are%20conflicting%20intervals%5Cn%22%3B%0A%20%20%20%20printConflicting(appt%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]Output:
Following are conflicting intervals [3,7] Conflicts with [1,5] [2,6] Conflicts with [1,5] [5,6] Conflicts with [3,7] [4,100] Conflicts with [1,5][ad type=”banner”]