Python - Brute Force ➜ Binary Search ➜ Min Heap ✅
1. BRUTE FORCE APPROACH - O(N^2)\n\nIn Brute Force approach, we just do what the problem asks us to do. We don\'t care about how efficient this solution is. But
## **1. BRUTE FORCE APPROACH - O(N^2)**\n\nIn Brute Force approach, we just do what the problem asks us to do. We don\'t care about how efficient this solution is. But if you are able to write a Brute Force Approach, you can think of an Optimized Solution easily.\n\nSince we are asked to find two non overlapping events, we can check for that by making sure that the second event starts after the first has finished. Since it is possible that for any ith event, an event with start time greater than end time of ith event can be before it in the list, we have to traverse the whole array from beginning for every event to find a valid event to pair. \n\nHence, this approach has an O(N^2) complexity. It will not work for large inputs and we will get TLE.\n\n\n    def maxTwoEvents(self, events: List[List[int]]) -> int:\n        maxSum = 0\n        \n        # For each event\n        for i in range(len(events)): \n            sum = events[i][2]\n            \n            # Try to find the event that can be paired with it to get a maximum sum\n            for j in range(len(events)):\n                if i != j and events[j][0] > events[i][1]:\n                    maxSum = max(maxSum, sum + events[j][2])            \n            \n            # This is for the cases when we cannot find any other event with which this event can be paired\n            # It is also possible that a single event has a higher value than any other valid pair combined\n            maxSum = max(maxSum, sum)\n        return maxSum\n\t\t\n## **2. BINARY SEARCH APPROACH - O(NLogN)**\n\nWe know that if an algorithm has O(N^2) time complexity and it is not working for large inputs, a better approach is to try to make it at least O(NLogN). \n\nConverting that N to LogN complexity means instead of Linear Search in the second for loop, we need to use Binary Search. But to use Binary Search, our array needs to be sorted. \n \nNotice that in Brute Force, one issue is that for each event, we have to traverse the list from the beginning to find an event whose start time is greater than the end time of ith event.\n\n\tNow, just think about it - What if our events list is already sorted based on start time?\n\n\tIn that case, if we can find an event that is valid, then all the events after it are also valid because array is sorted. \n\t\n\tConsider this example ->\n\t\n\t\t\tevents = [[1,3,2],[4,7,3],[5,8,5], [6,4,10]]\n\t\t\t\n\t\t\tIf we take the first event => [1,3,2]\n\t\t\t\n\t\t\tFor it, start time = 1 and end time = 3\n\t\t\t\n\t\t\tIt means, any event that has start time > 3 can be paired with this event.\n\t\t\t\n\t\t\tAnd we see that [4,7,3] is a valid event since its start time is 4 and 4 > 3\n\t\t\t\n\t\t\tBut since our list is already sorted based on start times, \n\t\t\tit also means, all events after [4,7,3] are also valid and can be paired with [1,3,2]\n\t\t\t\n\t\t\tNow you got the idea, right?\n\t\t\t\n\t\t\t\n\tSo, all that we need to find is this leftmost event that is valid \n\tbecause we know all events after it will be valid as well.\n\nOnce we can find such an index, then all that is left to find is what is the maximum possible value in [leftmostindex, end of list] subarray.\n\nBut if we try to find that for each event, that again results in an O(N^2) complexity because to find that max value in a certain interval, we again have to do linear scan as values are not sorted.\n\nHence, the only option is to find a way to precompute this maximum possible value on the right side of each index such that we can find the maximum value in any range [leftmostindex, end of list] in O(1) time.\n\nTherefore, before we even start with Binary Search, we have to precompute the maximum value on the right side for each event.\n\n```\ndef maxTwoEvents(self, events: List[List[int]]) -> int:\n        maxSum = 0\n        \n        n = len(events)\n        \n        # For Binary Search, we need Sorting first\n        # If we apply sort method to events, it will sort the events based on start time\n        events.sort()\n        \n        # Pre compute the maximum value on the right for each event\n        maxOnRight = [0] * n\n        \n        # For last event, there is no event on its right\n        # So for it, maximum is its value only\n        maxOnRight[- 1] = events[-1][2]\n        \n        for i in range(n - 2, -1, -1): maxOnRight[i] = max(events[i][2], maxOnRight[i + 1])\n        \n        # For each event\n        for i in range(n): \n            sum = events[i][2]\n            maxVal = 0\n\n            # Now, we can use Binary Search to find the leftmost valid event for ith event\n            # Because if we can find such an index, then all events after that index are also valid\n            # Because array is sorted based on start time \n            # so all events after that index will also have a start time greater than end time of ith event\n            start = i + 1\n            end = n - 1\n            leftmostValid = -1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                # IF mid is a valid event that we can consider pairing\n                # We can store this index as it may be the leftmost valid index\n                # But we keep searching on left of mid to find the leftmost if there is any other valid event on left\n                if events[mid][0] > events[i][1]:\n                    leftmostValid = mid\n                    end = mid - 1\n                    \n                # If mid itself is not valid, how can any event before mid can be valid?\n                else: start = mid + 1      \n                    \n            # Now, all that we want is what is the maximum value in the [leftmostValid, n - 1] subarray\n            # No need to find that again because we have precomputed that in the beginning\n            \n            if leftmostValid != -1: maxVal = maxOnRight[leftmostValid]\n                \n            maxSum = max(maxSum, sum + maxVal)\n        \n        return maxSum\n```\n\n## **3. MIN HEAP APPROACH - O(NLogN)**\n\nI found the minHeap logic to be quite similar to this problem that I did recently - https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/\n\nYou can find my solution and explanation here - https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/discuss/4134739/python-minheap-approach-explained\n\nIf you compare both the problems and solutions, you will see that one thing that\'s common in both is that we want to avoid overlapping intervals. So, somehow, we want to find a way to quickly check for these overlaps so that we don\'t have to loop over the entire list again and again for every event, something we will do in a Brute Force solution.\n\nOne thing to note is that whenever there is a problem around events/intervals where we have to take care of overlaps, sorting should be the first thing you should do. Why? Because, if we sort the data based on either the "start" or "end" value, then it become easier to check for overlaps. How?\n\n\tLet\'s take an example => events = [[1,3,2],[4,5,2],[2,4,3]]\n\t\n\tHere, in Brute Force approach, I have to take first event [1,3,2]\n\tand then loop over all other events to check for overlaps.\n\n\tSame for [4,5,2]. I will again loop over the entire list to check for overlaps.\n\t\n\tBut, now, sort the events based on their start values\n\t\n\tevents = [[1,3,2], [2,4,3], [4,5,2]]\n\t\n\tNow, since events are sorted by start value, we can say that an event "i" starts after or at the time the event "j" ends.\n\t\n\tAnd they both will overlap based on only one condition -> If event "i" starts before or at the time when event "i - 1" ends.\n\t\n\tIn other words, for both the events to not overlap, event "i" should start "after" event "i-1" ends.\n\t\n\tNow, we can improve our Brute Force solution a bit.\n\t\n\tBecause now, for every event, we just need to loop over all the events before it \n\tand see which "non-overlapping" event has the maximum value.\n\t\n\tBut again, this means, for every event, we have to loop over the entire list on the left.\n\tAnd here comes the minHeap logic.\n\t\nAs the name says, a minHeap will order the elements by some "value" such that the top of minheap has element with the least "value" and bottom has element with the maximum "value".\n\nHow can we use this to our advantage?\n\nFor any event "i", what if we know what is the event with smallest "end" time on its left? In that case, if the event "i" overlaps with the event with the smallest "end" time on its left, we can say that it overlaps with all the events on its left. Makes sense? In this way, there is no need to individually compare the events if we already know that the event "i" overlaps with the event that has smallest "end" value on left.\n\nNow, take the opposite case. If the event "i" does not overlap with the event with smallest "end" value on its left, can we way that all the events after "i" will also not overlap? ABSOLUTELY. Because we already sorted the events by their start values. So, any event after "i" will have a start value greater or equal to it only. \n\nSince we check overlap by checking if "start" of event "i" is greater than "end" of an event on left, this condition will be true for all events on right side of "i" if it is true for "i".\n\nAnd so, we can use a minHeap to quickly get the smallest end value on left so far. And in this way, we can easily get what is the maximum "value" of an event on the left that is not overlapping. Note that if the event with the smallest "end" value on left is not overlapping with an event "i", then we can simply update the maximum value on left so far and now, we no longer require this smallest "end" value event anymore since we know it won\'t be overlapping with any event on right side of "i". So, we can then move on to the next smaller "end" value event.\n\nAnd that\'s the reason we use a minHeap here - To quickly get the smallest end value event so far and compare it with current event.\n\n\n```\ndef maxTwoEvents(self, events: List[List[int]]) -> int:\n        \n        # Maximum Sum\n        maxSum = 0\n        \n        # Length of the list\n        n = len(events)\n        \n        # A Brute Force solution will fail\n        # Because, for every event, we have to loop over the whole list\n        # When it comes to intervals and sorting related problems, sorting is something we can use\n        # because sorting makes checking for overlaps easier\n        \n        # Let\'s sort the events by their start values\n        events.sort()\n        \n        # We want to quickly check for overlaps\n        # So, let\'s have a minHeap that keeps track of events so far from least end time to maximum\n        # Why minHeap? because, if an event overlaps with event on top of minHeap\n        # Ofcourse it will also overlap with all other events so far since they have end value\n        # greater or equal to what top of heap has \n        minHeap = []\n        \n        # What is the maximum "value" of an event so far before the current event that is not overlapping\n        maxValueSoFar = 0\n        \n        # Loop over the events\n        for event in events:\n            \n            # Our minHeap keeps the events by their "end" time from minimum to maximum\n            # So, the top of minHeap at any time has the event with the smallest end time so far\n            # So, if the current event overlaps that smallest end time event, ofcourse it will overlap with all events so far\n            # So in this way, we don\'t need to compare with all the events that occured so far\n            # Similarly, if the current event does not overlap with the top event\n            # Then we can say all the events after it also don\'t overlap since events are sorted by start values\n            while minHeap and event[0] > minHeap[0][0]: maxValueSoFar = max(maxValueSoFar, heappop(minHeap)[1])\n            \n            # Once we get the maximum possible "value" so far, we can update our maximum sum for the current "event"\n            # And note that this "maxValueSoFar" will remain a possible max value for all upcoming events\n            # Because as mentioned above, the list is sorted by "start" value\n            # It means, if for an event "i", we have a "maxValueSoFar", \n            # Then that will also be valid for any event at index greater than "i"\n            maxSum = max(maxSum, event[2] + maxValueSoFar)\n            \n            # Push the current event to the minHeap as well\n            heappush(minHeap, (event[1], event[2]))\n\n        # Return the maximum sum\n        return maxSum\n```\n\n
['Binary Search', 'Binary Tree', 'Python']