Solution for waifujahat | C# | 100% Both using Binary Search
\n\n---\n\n# How to solve\nThe goal of this task is to find the maximum sum of values by selecting at most two non-overlapping events, I need to ensure the two 
![Screenshot 2024-12-08 102114.png](https://assets.leetcode.com/users/images/a7b8414f-b60a-400c-8b9b-3aab58b971cb_1733628097.4585931.png)\n\n---\n\n# How to solve\nThe goal of this task is to find the maximum sum of values by selecting at most two non-overlapping events, I need to ensure the two chosen events don\'t overlap in their time intervals. Like another task I need to pay attention in constraint, it said for each event I choose, I must find another event that doesn\u2019t overlap. So I will make code with `Sorting` and could `Handle Ovelap` because `Sorting` allow us to easily identify future events that start after a given event ends and it make more easy to apply `Binary Search` and Binary Search used to find the earliest valid next event for a current event. Here my plan :\n1. Treat it as the first event\n2. Use Binary Search to find the best second event\n3. Use the suffix array to quickly get the value of the best second event\n4. Keep track of the maximum value across all combinations\n\n---\n\n# About my code\n\n1.  Sort events by start time\nSorting the events based on their start times ensures that when I process each event, all possible future events are in order and searching for a valid next event to attend. For each event, the potential future events are guaranteed to come later in the array, the code I make allows me to efficiently search for valid future events using binary search because future events are always sorted by their start time\n2. Prepare a Suffix Array for Maximum Values\nA suffix array stores the maximum value of events that start from a certain index onwards, here `suffix[i]` gives the maximum value of any event that starts at or after `events[i]`. My idea is to quickly find the best future event value when combining two events.\n3. I use Binary Search for Non-Overlapping Events\nI need to find the earliest event whose start time is strictly greater than the end time of the current event so I think Binary search is efficient way for this task because the events are sorted by start time, I could use another method but from the start I had planned to use Binary Search. So I just need to focus what I  so i just need to focus on my plan.\n4. Calculate the Maximum Value\nI keep a variable `value` to track the highest sum of values found and I will update it whenever a new valid combination is better than the current maximum, after checking all events, just return the maximum value found.\n\nFor example :\n![image.png](https://assets.leetcode.com/users/images/e13aca84-776c-42cc-b781-557aa0981537_1733665259.106132.png)\n\nInput = [[1, 3, 2], [4, 5, 2], [1, 5, 5]]\n1. Sorting\n[[1, 3, 2], [1, 5, 5], [4, 5, 2]]\n\n2. Suffix Array\nSuffix[2] = value of event[2] = 2\nSuffix[1] = max(suffix[2], value of event[1] = max(2, 5) = 5\nSuffix[0] = max(suffix[1], value of event[0] = max(5, 2) = 5\n[5, 5, 2]\n\n3. Binary Search\n~ `Event 0` - [1, 3, 2]\nEvents`[mid][0] > 3`\nBinary search find `Event 2` = [4, 5, 2]\nCalculate total value :\nCurrent = 2 | suffix[2]: 2 | 2 + 2 = 4 | current = `4`\n~ `Event 1` - [1, 5, 5]\nEvents`[mid][0] > 5`\nBinary search fails to find a valid next event because no events start after time 5\nCalculate total value :\nCurrent = 5 | No next event to combine | current = `5`\n~ `Event 2` - [4, 5, 2]\nEvents`[mid][0] > 5`\nBinary search fails to find a valid next event because no events start after time 5\nCalculate total value :\nCurrent = 2 | No next event to combine | current = `5`\n\n4. The highest total value of two non overlapping events is 5, achieved by selecting `Event 1` [1, 5, 5], return value = `5`\n\n---\n\n# Code\n```csharp []\npublic class Solution {\n    public int MaxTwoEvents(int[][] events) {\n        int n = events.Length;\n\n        // Step 1\n        // Sort events by start time\n        Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));\n\n        // Step 2\n        // Prepare suffix array for maximum future values\n        int[] suffix = new int[n];\n        suffix[n - 1] = events[n - 1][2];\n\n        // Fill the array with the maximum values of events starting after the current event\n        // Suffix array from right to left\n        for (int i = n - 2; i >= 0; i--) \n        {\n            suffix[i] = Math.Max(suffix[i + 1], events[i][2]);\n        }\n\n        // To store or initialize max value\n        int value = 0;\n\n        // Step 3 \n        // Iterate over each event to find the best combination\n        for (int i = 0; i < n; i++) \n        {\n            // Step 4\n            // Binary search for the next valid event\n            int current = events[i][2];\n            // Update max value with current event alone\n            value = Math.Max(value, current); \n            int low = i + 1;\n            int high = n - 1;\n            int nextevent = -1;\n\n            while (low <= high) \n            {\n                int mid = low + (high - low) / 2;\n\n                // Check if the event at mid starts after the current event ends\n                if (events[mid][0] > events[i][1]) \n                {\n                    nextevent = mid;\n                    high = mid - 1;\n                } \n                else \n                {\n                    low = mid + 1;\n                }\n            }\n            // Step 5\n            // Calculate the sum of current and next events values\n            // If a valid next event is found, calculate the total value current + next\n            if (nextevent != -1) \n            {\n                value = Math.Max(value, current + suffix[nextevent]);\n            }\n        }\n        // Return the maximum value found\n        return value;\n    }\n}\n\n```
['Array', 'Binary Search', 'Dynamic Programming', 'Sorting', 'Heap (Priority Queue)', 'C#']