🏆 Binary Search & Max Value Tracking || ~25ms in Rust & Go || Brief and Clear Description
\uD83D\uDE07 Intuition\n\nTo maximize the sum of values from two non-overlapping events, we leverage the sorted order of events by $end\_time$ to efficiently fi
# \uD83D\uDE07 Intuition\n\nTo maximize the sum of values from two non-overlapping events, we leverage the sorted order of events by $end\\_time$ to efficiently find the best candidate for the second event using binary search. Sorting helps us ensure __efficient lookup__ for compatible events, while a __right-to-left max-value array__ keeps track of the best values for subsequent choices.\n\n# \uD83D\uDEE0\uFE0F Approach\n\n1. __Sort Events:__ Sort events by $end\\_time$ in <ins>descending order</ins> to facilitate binary search for the first compatible event.\n2. __Precompute Maximum Values:__ Use a $max\\_vals$ array to store the maximum value achievable for all events to the right of the <ins>current event</ins>.\n3. __Iterate and Search:__\n    - For each event, compute the value if it\u2019s chosen as the first event.\n    - Use <ins>binary search</ins> to find the first event that ends before this event starts.\n    - Combine the values of these two events and update the $best$ result.\n\n# Complexity\n- __\u23F1\uFE0F Time Complexity__\n    - <ins>Sorting</ins>: $O(n\\ log\u2061n)$, where $n$ is the number of events.\n    - <ins>Binary Search</ins> for Each Event: $O(n\\ log\u2061n)$.\n    - <ins>Total</ins>: $O(n\\ log\u2061n)$.\n\n- __\uD83D\uDEE0\uFE0F Space Complexity__\n    - <ins>Extra Space</ins> for $max\\_vals$: $O(n)$.\n    - <ins>In-place Sorting</ins>: $O(1)$\n\n# Code\n```rust []\nimpl Solution {\n    pub fn max_two_events(events: Vec<Vec<i32>>) -> i32 {\n        let mut events = events;\n\n        // Sort events by end time in descending order\n        events.sort_by(|a, b| b[1].cmp(&a[1]));\n\n        let n = events.len();\n        let mut max_vals = vec![0; n + 1]; // To store max values from right to left\n\n        // Populate max_vals array with maximum values from right to left\n        for i in (0..n).rev() {\n            max_vals[i] = max_vals[i + 1].max(events[i][2]);\n        }\n\n        let mut best = 0;\n\n        // Iterate over each event to find the best combination\n        for i in 0..n {\n            let current_value = events[i][2];\n\n            // Binary search for the first event that ends before the current event starts\n            let end_time = events[i][0] - 1;\n            let idx = events.binary_search_by(|event| end_time.cmp(&event[1]))\n                .unwrap_or_else(|x| x);\n\n            let total_value = if idx < n { current_value + max_vals[idx] } else { current_value };\n\n            // Update the best value\n            best = best.max(total_value);\n        }\n\n        best\n    }\n}\n```\n``` Go []\nimport (\n    "sort"\n)\n\nfunc maxTwoEvents(events [][]int) int {\n    // Sort events by end time in descending order\n    sort.Slice(events, func(i, j int) bool {\n        return events[i][1] > events[j][1]\n    })\n\n    n := len(events)\n    maxVals := make([]int, n+1) // To store max values from the end to the beginning\n    maxVals[n] = 0              // Initialize the value after the last event as 0\n\n    // Populate maxVals array with maximum values from right to left\n    for i := n - 1; i >= 0; i-- {\n        maxVals[i] = max(maxVals[i+1], events[i][2])\n    }\n\n    best := 0\n\n    // Iterate over each event to find the best combination\n    for i := 0; i < n; i++ {\n        currentValue := events[i][2]\n        // Binary search for the first event that ends before the current event starts\n        idx := sort.Search(n, func(j int) bool {\n            return events[j][1] < events[i][0]\n        })\n        if idx < n {\n            currentValue += maxVals[idx]\n        }\n        best = max(best, currentValue)\n    }\n\n    return best\n}\n\n// max is a helper function to find the maximum of two integers.\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n```
['Array', 'Binary Search', 'Go', 'Rust']