100% Beats Simple Binary Search
Solution Explanation: Maximizing the Sum of Two Non-overlapping Events \uD83C\uDF1F\n\n## Intuition \uD83D\uDCA1\nThe problem asks us to select at most two non-
# Solution Explanation: Maximizing the Sum of Two Non-overlapping Events \uD83C\uDF1F\n\n## Intuition \uD83D\uDCA1\nThe problem asks us to select at most two non-overlapping events such that the sum of their values is maximized. The key challenge is ensuring that the two selected events do not overlap. We need an approach that allows us to efficiently find the best combination of two events.\n\n### Thought Process \uD83E\uDDE0:\n1. **Event Structure**: Each event is represented by three values: the **start time**, the **end time**, and the **value**. The goal is to choose two events where one starts strictly after the other ends. The more valuable the event, the better, so we want to maximize the sum of their values.\n   \n2. **Sorting by Start Time** \uD83D\uDCC5: One of the first things we can do to organize the events is to sort them by their start time. This makes it easier to look ahead at events that may be a valid candidate for pairing.\n\n3. **Avoid Redundancy with a Suffix Array** \uD83D\uDD04: Instead of searching for the best second event for every single event, we can create a **suffix array** that stores the maximum possible value for non-overlapping events that occur after a given event. This allows us to quickly get the best possible event for pairing, saving us from redundant checks.\n\n4. **Efficient Searching with Binary Search** \uD83D\uDD0D: After sorting the events, we can use **binary search** to find the next valid event that starts after the current event ends. This ensures that we can efficiently check for valid pairs without having to iterate over all subsequent events.\n\n---\n\n## Approach \uD83D\uDD27\n\n### 1. Sort Events by Start Time \uD83D\uDCCA\nThe first step is to sort the events based on their **start time**. This way, we process each event in chronological order, making it easy to find the subsequent event that starts after the current event ends. Sorting ensures that we can quickly identify events that may or may not overlap with the current one.\n\n### 2. Create a Suffix Array \uD83D\uDDC2\nWe create a **suffix array** to keep track of the maximum possible value of non-overlapping events from the current event to the last event. The idea behind the suffix array is simple:\n- Start by initializing the last event\u2019s value as the maximum value.\n- Then, working backwards through the list of events, update the suffix array with the highest event value encountered so far.\n- This array allows us to quickly access the best possible future event without needing to repeatedly check all future events.\n\n### 3. Binary Search for Non-overlapping Events \uD83D\uDD0D\nFor each event, we need to find the first event that starts after the current event ends. Since the events are sorted by start time, we can use **binary search** to efficiently find this next valid event. If no such event exists, we just move on to the next one. If a valid event is found, we can easily retrieve its value from the suffix array and calculate the total value.\n\n### 4. Maximize the Total Value \uD83D\uDCB8\nFor each event:\n- First, we check if attending only this event yields a higher value than the current maximum sum.\n- Then, if a valid second event is found (using the binary search), we calculate the sum of the current event\u2019s value and the best possible future event value (from the suffix array).\n- We update the maximum sum accordingly, ensuring that we track the best combination of non-overlapping events.\n\n---\n\n## Complexity \uD83D\uDCC8\n\n- **Time Complexity** \u23F1\uFE0F:\n    - **Sorting** the events by their start time takes \\(O(n \\log n)\\).\n    - For each event, **binary search** is used to find the next event that starts after the current event ends, which takes \\(O(\\log n)\\).\n    - Therefore, the overall time complexity is \\(O(n \\log n)\\), where \\(n\\) is the number of events.\n\n- **Space Complexity** \uD83D\uDCE6:\n    - We use an array of size \\(n\\) to store the **suffix maximum values**. This space is necessary to store the maximum values of non-overlapping events starting from each index.\n    - Therefore, the space complexity is \\(O(n)\\).\n![Screenshot 2024-12-08 075554.png](https://assets.leetcode.com/users/images/896ea877-5562-4f75-92b7-2fe555b5fd6c_1733624862.2201223.png)\n\n\n---\n\n## Key Insights \u2728\n\n### Sorting by Start Time \uD83D\uDDD3\uFE0F\nBy sorting the events by their start time, we ensure that we can efficiently look ahead for the next valid event. This helps us structure the problem in a way that allows for efficient searching and avoids unnecessary checks.\n\n### Binary Search for Next Event \uD83D\uDD0D\nBinary search helps us find the first event that starts after the current event ends in **logarithmic time**. This ensures that we are not wasting time checking each event one by one.\n\n### Suffix Array for Max Values \uD83D\uDC8E\nThe suffix array provides a quick way to access the best possible non-overlapping event from the current event onward. It allows us to avoid recalculating the maximum for every event, which saves time and makes the solution efficient.\n\n### Efficient Pairing of Events \uD83D\uDD17\nThe combination of sorting, binary search, and the suffix array makes the solution very efficient in finding the best pair of non-overlapping events. It allows us to maximize the sum of the values in \\(O(n \\log n)\\) time, which is optimal for this problem.\n\n---\n\nThis approach efficiently solves the problem while ensuring that we minimize unnecessary computations. The use of sorting, binary search, and the suffix array ensures that the solution is both time-efficient and easy to understand. \uD83C\uDF89\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        int n = events.size();\n        \n        sort(events.begin(), events.end(), [](const vector<int>& a, const vector<int>& b) {\n            return a[0] < b[0];\n        });\n        \n        vector<int> suffixMax(n);\n        suffixMax[n - 1] = events[n - 1][2];\n        \n        for (int i = n - 2; i >= 0; --i) {\n            suffixMax[i] = max(events[i][2], suffixMax[i + 1]);\n        }\n        \n        int maxSum = 0;\n        \n        for (int i = 0; i < n; ++i) {\n            int left = i + 1, right = n - 1;\n            int nextEventIndex = -1;\n            \n            while (left <= right) {\n                int mid = left + (right - left) / 2;\n                if (events[mid][0] > events[i][1]) {\n                    nextEventIndex = mid;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            \n            if (nextEventIndex != -1) {\n                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex]);\n            }\n            \n            maxSum = max(maxSum, events[i][2]);\n        }\n        \n        return maxSum;\n    }\n};\n\n```\n```Python3 []\nfrom typing import List\n\nclass Solution:\n    def maxTwoEvents(self, events: List[List[int]]) -> int:\n        n = len(events)\n        \n        # Step 1: Sort the events by their start time\n        events.sort(key=lambda x: x[0])\n        \n        # Step 2: Create the suffix array for the maximum event value from each event onward\n        suffixMax = [0] * n\n        suffixMax[n - 1] = events[n - 1][2]  # Initialize the last event\'s value\n        \n        # Populate the suffixMax array\n        for i in range(n - 2, -1, -1):\n            suffixMax[i] = max(events[i][2], suffixMax[i + 1])\n        \n        # Step 3: For each event, find the next event that starts after it ends\n        maxSum = 0\n        \n        for i in range(n):\n            left, right = i + 1, n - 1\n            nextEventIndex = -1\n            \n            # Perform binary search to find the next non-overlapping event\n            while left <= right:\n                mid = left + (right - left) // 2\n                if events[mid][0] > events[i][1]:\n                    nextEventIndex = mid\n                    right = mid - 1\n                else:\n                    left = mid + 1\n            \n            # If a valid next event is found, update the max sum\n            if nextEventIndex != -1:\n                maxSum = max(maxSum, events[i][2] + suffixMax[nextEventIndex])\n            \n            # Also consider the case where we take only the current event\n            maxSum = max(maxSum, events[i][2])\n        \n        return maxSum\n\n```\n```Java []\nimport java.util.*;\n\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        int n = events.length;\n        \n        // Step 1: Sort the events by their start time\n        Arrays.sort(events, (a, b) -> a[0] - b[0]);\n        \n        // Step 2: Create the suffix array for the maximum event value from each event onward\n        int[] suffixMax = new int[n];\n        suffixMax[n - 1] = events[n - 1][2];  // Initialize the last event\'s value\n        \n        // Populate the suffixMax array\n        for (int i = n - 2; i >= 0; --i) {\n            suffixMax[i] = Math.max(events[i][2], suffixMax[i + 1]);\n        }\n        \n        // Step 3: For each event, find the next event that starts after it ends\n        int maxSum = 0;\n        \n        for (int i = 0; i < n; ++i) {\n            int left = i + 1, right = n - 1;\n            int nextEventIndex = -1;\n            \n            // Perform binary search to find the next non-overlapping event\n            while (left <= right) {\n                int mid = left + (right - left) / 2;\n                if (events[mid][0] > events[i][1]) {\n                    nextEventIndex = mid;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            \n            // If a valid next event is found, update the max sum\n            if (nextEventIndex != -1) {\n                maxSum = Math.max(maxSum, events[i][2] + suffixMax[nextEventIndex]);\n            }\n            \n            // Also consider the case where we take only the current event\n            maxSum = Math.max(maxSum, events[i][2]);\n        }\n        \n        return maxSum;\n    }\n}\n\n```\n```C# []\npublic class Solution {\n    public int MaxTwoEvents(int[][] events) {\n        int n = events.Length;\n        \n        // Step 1: Sort the events by their start time\n        Array.Sort(events, (a, b) => a[0].CompareTo(b[0]));\n        \n        // Step 2: Create the suffix array for the maximum event value from each event onward\n        int[] suffixMax = new int[n];\n        suffixMax[n - 1] = events[n - 1][2];  // Initialize the last event\'s value\n        \n        // Populate the suffixMax array\n        for (int i = n - 2; i >= 0; i--) {\n            suffixMax[i] = Math.Max(events[i][2], suffixMax[i + 1]);\n        }\n        \n        // Step 3: For each event, find the next event that starts after it ends\n        int maxSum = 0;\n        \n        for (int i = 0; i < n; i++) {\n            int left = i + 1, right = n - 1;\n            int nextEventIndex = -1;\n            \n            // Perform binary search to find the next non-overlapping event\n            while (left <= right) {\n                int mid = left + (right - left) / 2;\n                if (events[mid][0] > events[i][1]) {\n                    nextEventIndex = mid;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n            \n            // If a valid next event is found, update the max sum\n            if (nextEventIndex != -1) {\n                maxSum = Math.Max(maxSum, events[i][2] + suffixMax[nextEventIndex]);\n            }\n            \n            // Also consider the case where we take only the current event\n            maxSum = Math.Max(maxSum, events[i][2]);\n        }\n        \n        return maxSum;\n    }\n}\n\n```\n```Ruby []\n# @param {Integer[][]} events\n# @return {Integer}\ndef max_two_events(events)\n    # Step 1: Sort the events by their start time\n    events.sort_by! { |event| event[0] }\n\n    # Step 2: Create the suffix array for the maximum event value from each event onward\n    n = events.length\n    suffix_max = Array.new(n)\n    suffix_max[n - 1] = events[n - 1][2]  # Initialize the last event\'s value\n\n    # Populate the suffix_max array\n    (n - 2).downto(0) do |i|\n        suffix_max[i] = [events[i][2], suffix_max[i + 1]].max\n    end\n\n    # Step 3: For each event, find the next event that starts after it ends\n    max_sum = 0\n\n    (0...n).each do |i|\n        left, right = i + 1, n - 1\n        next_event_index = -1\n\n        # Perform binary search to find the next non-overlapping event\n        while left <= right\n            mid = left + (right - left) / 2\n            if events[mid][0] > events[i][1]\n                next_event_index = mid\n                right = mid - 1\n            else\n                left = mid + 1\n            end\n        end\n\n        # If a valid next event is found, update max_sum\n        if next_event_index != -1\n            max_sum = [max_sum, events[i][2] + suffix_max[next_event_index]].max\n        end\n\n        # Also consider the case where we take only the current event\n        max_sum = [max_sum, events[i][2]].max\n    end\n\n    max_sum\nend\n```\n```javascript []\n/**\n * @param {number[][]} events\n * @return {number}\n */\nvar maxTwoEvents = function(events) {\n    const n = events.length;\n    \n    // Step 1: Sort the events by their start time\n    events.sort((a, b) => a[0] - b[0]);\n    \n    // Step 2: Create the suffix array for the maximum event value from each event onward\n    let suffixMax = new Array(n);\n    suffixMax[n - 1] = events[n - 1][2];  // Initialize the last event\'s value\n    \n    // Populate the suffixMax array\n    for (let i = n - 2; i >= 0; i--) {\n        suffixMax[i] = Math.max(events[i][2], suffixMax[i + 1]);\n    }\n    \n    // Step 3: For each event, find the next event that starts after it ends\n    let maxSum = 0;\n    \n    for (let i = 0; i < n; i++) {\n        let left = i + 1, right = n - 1;\n        let nextEventIndex = -1;\n        \n        // Perform binary search to find the next non-overlapping event\n        while (left <= right) {\n            let mid = Math.floor((left + right) / 2);\n            if (events[mid][0] > events[i][1]) {\n                nextEventIndex = mid;\n                right = mid - 1;\n            } else {\n                left = mid + 1;\n            }\n        }\n        \n        // If a valid next event is found, update the max sum\n        if (nextEventIndex !== -1) {\n            maxSum = Math.max(maxSum, events[i][2] + suffixMax[nextEventIndex]);\n        }\n        \n        // Also consider the case where we take only the current event\n        maxSum = Math.max(maxSum, events[i][2]);\n    }\n    \n    return maxSum;\n};\n```\n```Rust []\nimpl Solution {\n    pub fn max_two_events(events: Vec<Vec<i32>>) -> i32 {\n        let n = events.len();\n\n        // Step 1: Sort the events by their start time\n        let mut events = events;\n        events.sort_by(|a, b| a[0].cmp(&b[0]));\n\n        // Step 2: Create the suffix array for the maximum event value from each event onward\n        let mut suffix_max = vec![0; n];\n        suffix_max[n - 1] = events[n - 1][2];  // Initialize the last event\'s value\n        \n        // Populate the suffix_max array\n        for i in (0..n - 1).rev() {\n            suffix_max[i] = suffix_max[i + 1].max(events[i][2]);\n        }\n\n        // Step 3: For each event, find the next event that starts after it ends\n        let mut max_sum = 0;\n\n        for i in 0..n {\n            let mut left = i + 1;\n            let mut right = n - 1;\n            let mut next_event_index = -1;\n\n            // Perform binary search to find the next non-overlapping event\n            while left <= right {\n                let mid = left + (right - left) / 2;\n                if events[mid][0] > events[i][1] {\n                    next_event_index = mid as i32;\n                    right = mid - 1;\n                } else {\n                    left = mid + 1;\n                }\n            }\n\n            // If a valid next event is found, update max_sum\n            if next_event_index != -1 {\n                let next_event_index = next_event_index as usize;\n                max_sum = max_sum.max(events[i][2] + suffix_max[next_event_index]);\n            }\n\n            // Also consider the case where we take only the current event\n            max_sum = max_sum.max(events[i][2]);\n        }\n\n        max_sum\n    }\n}\n\n```
['Binary Search', 'C', 'Sorting', 'C++', 'Java', 'Python3', 'Rust', 'Ruby', 'JavaScript', 'C#']