{"id":26837,"date":"2018-01-05T21:32:57","date_gmt":"2018-01-05T16:02:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26837"},"modified":"2018-01-05T21:32:57","modified_gmt":"2018-01-05T16:02:57","slug":"c-programming-given-n-appointments-find-conflicting-appointments","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-given-n-appointments-find-conflicting-appointments\/","title":{"rendered":"C++ Programming &#8211; Given n appointments, find all conflicting appointments"},"content":{"rendered":"<p>Given n appointments, find all conflicting appointments.<span id=\"more-132992\"><\/span><\/p>\n<p>Examples:<\/p>\n<pre>Input: appointments[] = { {1, 5} {3, 7}, {2, 6}, {10, 15}, {5, 6}, {4, 100}}\r\nOutput: Following are conflicting intervals\r\n[3,7] Conflicts with [1,5]\r\n[2,6] Conflicts with [1,5]\r\n[5,6] Conflicts with [3,7]\r\n[4,100] Conflicts with [1,5]<\/pre>\n<p>An appointment is conflicting, if it conflicts with any of the previous appointments in array.<\/p>\n[ad type=\u201dbanner\u201d]\n<p>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, \u2026 0. The time complexity of this method is O(n2).<\/p>\n<p>We can use Interval Tree to solve this problem in O(nLogn) time. Following is detailed algorithm.<\/p>\n<pre>1) Create an Interval Tree, initially with the first appointment.\r\n2) Do following for all other appointments starting from the second one.\r\n   a) Check if the current appointment conflicts with any of the existing \r\n     appointments in Interval Tree.  If conflicts, then print the current\r\n     appointment.  This step can be done O(Logn) time.\r\n   b) Insert the current appointment in Interval Tree. This step also can\r\n      be done O(Logn) time.<\/pre>\n<p>Following is C++ implementation of above idea.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%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\u2019i\u2019%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\u2019s%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\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Following are conflicting intervals\r\n[3,7] Conflicts with [1,5]\r\n[2,6] Conflicts with [1,5]\r\n[5,6] Conflicts with [3,7]\r\n[4,100] Conflicts with [1,5]<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>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, \u2026 <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1],"tags":[80003,79997,80006,80002,79994,80005,79992,80007,80010,79999,80009,80014,79998,79987,80008,80004],"class_list":["post-26837","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","tag-decline-meeting-invitation-sample","tag-define-conflict","tag-email-for-meeting-request","tag-english-message","tag-how-to-schedule-meeting-in-outlook","tag-how-to-taking-english","tag-meaning-of-conflict","tag-meeting-acceptance-email","tag-meeting-appointment-email","tag-meeting-invitation-email","tag-meeting-request-message","tag-outlook-booking-meeting-rooms","tag-outlook-meeting-request","tag-outlook-meeting-room-booking","tag-reschedule-meeting-email","tag-resource-scheduling"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26837","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26837"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26837\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26837"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26837"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26837"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}