✅Maximum Sum of Two Non-Overlapping Events Using Binary Search🚀Beats💯
Intuition:\n\nTo maximize the sum of values of two non-overlapping events, we need to:\n1. Identify two events such that their times do not overlap (i.e., the s
# Intuition:\n\nTo maximize the sum of values of two non-overlapping events, we need to:\n1. Identify two events such that their times do not overlap (i.e., the start time of one is after the end time of the other).\n2. Leverage the sorted structure of events to efficiently find compatible pairs, maximizing their combined values.\n\nA **binary search** approach is suitable for finding the latest non-overlapping event efficiently.\n\n# Approach:\n\n1. **Sort Events by End Time**:\n    - Sorting events by their end time helps to easily determine compatibility using binary search.\n2. **Binary Search for Compatibility**:\n    - For each event, find the latest event (ending before the current event starts) using binary search.\n3. **Precompute Maximum Values**:\n    - To optimize the selection of the second event, maintain a prefix array where `maxValues[i]` holds the maximum value of events from the start up to the ith event.\n4. **Iterate Over Events**:\n    - For each event:\n        - Use binary search to find the latest non-overlapping event.\n        - Calculate the maximum sum of the current event and the best earlier event.\n5. **Result**:    \n    - The result is the maximum of the sums computed during the iteration.\n\n# Complexity:\n\n- **Time Complexity**:\n    - Sorting: ***O(n log\u2061 n)***\n    - Binary search for each event: ***O(n log \u2061n)***\n    - Total: ***O(n log \u2061n)***\n- **Space Complexity**:\n    - ***O(n)*** for storing `maxValues` and sorted events.\n\n# Code:\n\n```typescript\nfunction maxTwoEvents(events: number[][]): number {\n    // Sort events by endTime\n    events.sort((a, b) => a[1] - b[1]);\n\n    const n = events.length;\n    const maxValues = new Array(n).fill(0);\n\n    // Precompute maxValues to store the max value up to each event\n    maxValues[0] = events[0][2];\n    for (let i = 1; i < n; i++) {\n        maxValues[i] = Math.max(maxValues[i - 1], events[i][2]);\n    }\n\n    let maxSum = 0;\n\n    for (let i = 0; i < n; i++) {\n        const [startTime, endTime, value] = events[i];\n\n        // Binary search to find the last event that ends before startTime\n        let low = 0, high = i - 1, lastCompatible = -1;\n        while (low <= high) {\n            const mid = Math.floor((low + high) / 2);\n            if (events[mid][1] < startTime) {\n                lastCompatible = mid;\n                low = mid + 1;\n            } else {\n                high = mid - 1;\n            }\n        }\n\n        // If a compatible event exists, calculate the sum\n        const currentSum = value + (lastCompatible !== -1 ? maxValues[lastCompatible] : 0);\n\n        // Update the maximum sum\n        maxSum = Math.max(maxSum, currentSum);\n    }\n\n    return maxSum;\n};\n\n```\n\n---\n\n### **Example and Explanation Walkthrough**:\n\n#### Example 1:\n\n**Input**:\n```typescript\nevents = [[1,3,2],[4,5,2],[2,4,3]];\n```\n\n**Execution**:\n1. Sort events: `[[1,3,2], [2,4,3], [4,5,2]]`.\n2. Precompute `maxValues`:\n    - `maxValues = [2, 3, 3]`.\n3. Iterate over events:\n    - For event `[1,3,2]`: No previous compatible event. Max sum = `2`.\n    - For event `[2,4,3]`: No previous compatible event. Max sum = `3`.\n    - For event `[4,5,2]`: Compatible with `[1,3,2]`. Max sum = `2 + 2 = 4`.\n4. **Output**: `4`.\n\n#### Example 2:\n\n**Input**:\n```typescript\nevents = [[1,5,3],[1,5,1],[6,6,5]];\n```\n\n**Execution**:\n1. Sort events: `[[1,5,3], [1,5,1], [6,6,5]]`.\n2. Precompute `maxValues`:\n    - `maxValues = [3, 3, 5]`.\n3. Iterate over events:\n    - For event `[1,5,3]`: No previous compatible event. Max sum = `3`.\n    - For event `[1,5,1]`: No previous compatible event. Max sum = `3`.\n    - For event `[6,6,5]`: Compatible with `[1,5,3]`. Max sum = `3 + 5 = 8`.\n4. **Output**: `8`.\n\n---\n\n### **Key Insights**:\n\n- **Binary Search** ensures efficient compatibility checks.\n- **Precomputing Maximum Values** allows fast retrieval of the best earlier event\'s value.\n- The approach works well within the constraints.
['TypeScript']