Python | Greedy & Binary Search
see the Successfully Accepted Submission\n\n# Code\npython3 []\nclass Solution:\n    def maxTwoEvents(self, events: List[List[int]]) -> int:\n        # Step 1: 
[see the Successfully Accepted Submission](https://leetcode.com/problems/two-best-non-overlapping-events/submissions/1473126424/?envType=daily-question&envId=2024-12-08)\n\n# Code\n```python3 []\nclass Solution:\n    def maxTwoEvents(self, events: List[List[int]]) -> int:\n        # Step 1: Sort the events based on their end time\n        events.sort(key=lambda x: x[1])\n        \n        # Step 2: Maintain a list of [endTime, max_value_until_now]\n        max_until = []\n        max_value = 0\n        for _, end, value in events:\n            max_value = max(max_value, value)\n            max_until.append((end, max_value))\n        \n        # Step 3: Find the maximum sum of two events\n        result = 0\n        for start, end, value in events:\n            # Option 1: Take the current event alone\n            result = max(result, value)\n            \n            # Option 2: Take another event that ends before this one starts\n            idx = bisect.bisect_left(max_until, (start, 0)) - 1\n            if idx >= 0:\n                result = max(result, value + max_until[idx][1])\n        \n        return result\n\n```\n\n# Explanation \n\n## Sorting the Events:\n- The events are sorted by their end times to facilitate the lookup of non-overlapping events.\n\n## Precomputing Maximum Values:\n- We maintain a list `max_until` where each entry `(endTime, max_value_until_now)` represents the maximum value achievable by any event ending on or before that time.\n- This is updated iteratively as we traverse the sorted events.\n\n## Binary Search:\n- For each event, we use binary search (`bisect_left`) to find the last event in `max_until` that ends before the current event\'s start time.\n- This ensures that the selected events are non-overlapping.\n\n## Result Calculation:\n- The result is updated with the maximum of:\n  1. The value of the current event alone.\n  2. The sum of the current event and the maximum value of a non-overlapping event.\n\n## Complexity:\n### Time Complexity:\n- **Sorting the events**: \\(O(n \\log n)\\)\n- **For each event, a binary search**: \\(O(n \\log n)\\)\n- **Overall**: \\(O(n \\log n)\\)\n\n### Space Complexity:\n- \\(O(n)\\) due to the `max_until` list.\n\n\n![image](https://assets.leetcode.com/users/images/b1e4af48-4da1-486c-bc97-b11ae02febd0_1696186577.992237.jpeg)
['Python3']