🔥BEATS 💯 % 🎯 |✨SUPER EASY BEGINNERS 👏
\n\n## MOST IMP POINT\n###  At most two non-overlapping \n\n\n\n\n\n\n---\nHere\u2019s the detailed breakdown of the problem-solving process for maximizing the 
![image.png](https://assets.leetcode.com/users/images/df80087f-7ffc-48c1-94a0-185718d3923b_1733648929.941429.png)\n\n## MOST IMP POINT\n###  At most two non-overlapping \n\n![1000028386.png](https://assets.leetcode.com/users/images/3efa41c6-e350-4e3c-b9c9-189456a98878_1733661169.9060109.png)\n\n\n\n\n---\nHere\u2019s the detailed breakdown of the problem-solving process for maximizing the sum of values of at most two non-overlapping events:\n\n---\n\n# Intuition\nThe goal is to select up to two non-overlapping events such that their combined value is maximized.  \n- To efficiently check overlapping conditions, **sorting the events by end time** is beneficial.  \n- A **binary search** can be used to quickly find the latest event that does not overlap with the current one.  \n- We use a **running maximum array** to keep track of the maximum value from earlier events, ensuring efficient calculation of the maximum sum.\n\n---\n\n# Approach\n### Step 1: Sort Events by End Time\n- Sorting events by their end times helps in managing overlapping efficiently. This way, for each event, we only need to look at earlier events for potential inclusion.\n\n### Step 2: Create a Running Maximum Array\n- A `maxValues` array is used to store the maximum value among all events up to the current event (non-overlapping logic considered via binary search).\n- This allows efficient calculation of the sum for a given pair of events.\n\n### Step 3: Iterate Through Events\n- For each event:\n  - Use binary search to find the latest event that ends before the current event starts.\n  - Add its value (if it exists) to the current event\'s value.\n  - Update the global maximum sum if the resulting sum is larger than the previous maximum.\n\n### Step 4: Binary Search for Non-Overlapping Events\n- The binary search is used to find the index of the latest event that ends before the current event starts. This ensures no overlap between the selected events.\n\n---\n\n# Complexity\n- **Time Complexity:**  \n  - Sorting: $$O(n \\log n)$$  \n  - Binary Search for each event: $$O(n \\log n)$$  \n  - Total: $$O(n \\log n)$$.\n\n- **Space Complexity:**  \n  - Running max array: $$O(n)$$  \n  - Total: $$O(n)$$.\n\n---\n\n\n```dart []\nimport \'dart:math\';\n\nclass Solution {\n  int maxTwoEvents(List<List<int>> events) {\n    // Step 1: Sort events by their end times\n    events.sort((a, b) => a[1].compareTo(b[1]));\n\n    // Step 2: Create a running max array\n    int n = events.length;\n    List<int> maxValues = List.filled(n, 0);\n    maxValues[0] = events[0][2]; // Value of the first event\n\n    // Fill the running max array\n    for (int i = 1; i < n; i++) {\n      maxValues[i] = max(maxValues[i - 1], events[i][2]);\n    }\n\n    int maxSum = 0;\n\n    // Step 3: Iterate through the events and use binary search\n    for (int i = 0; i < n; i++) {\n      int start = events[i][0];\n      int value = events[i][2];\n\n      // Find the latest event that ends before the current event starts\n      int idx = binarySearch(events, start - 1);\n\n      // If a valid previous event is found, calculate the sum\n      int currentSum = value;\n      if (idx != -1) currentSum += maxValues[idx];\n\n      // Update the global maximum sum\n      maxSum = max(maxSum, currentSum);\n    }\n\n    return maxSum;\n  }\n\n  // Helper: Binary search to find the latest event that ends <= targetEnd\n  int binarySearch(List<List<int>> events, int targetEnd) {\n    int start = 0, end = events.length - 1, res = -1;\n\n    while (start <= end) {\n      int mid = start + (end - start) ~/ 2;\n      if (events[mid][1] <= targetEnd) {\n        res = mid; // Found a valid event\n        start = mid + 1; // Try to find a later one\n      } else {\n        end = mid - 1;\n      }\n    }\n\n    return res;\n  }\n}\n```\n\n\n```python []\nclass Solution:\n    def maxTwoEvents(self, events: List[List[int]]) -> int:\n        # Step 1: Sort events by their end times\n        events.sort(key=lambda x: x[1])\n\n        # Step 2: Create a running max array\n        n = len(events)\n        maxValues = [0] * n\n        maxValues[0] = events[0][2]\n\n        for i in range(1, n):\n            maxValues[i] = max(maxValues[i - 1], events[i][2])\n\n        maxSum = 0\n\n        # Step 3: Iterate through the events and use binary search\n        for i in range(n):\n            start, value = events[i][0], events[i][2]\n            idx = self.binarySearch(events, start - 1)\n\n            currentSum = value\n            if idx != -1:\n                currentSum += maxValues[idx]\n\n            maxSum = max(maxSum, currentSum)\n\n        return maxSum\n\n    def binarySearch(self, events, targetEnd):\n        start, end = 0, len(events) - 1\n        res = -1\n\n        while start <= end:\n            mid = start + (end - start) // 2\n            if events[mid][1] <= targetEnd:\n                res = mid\n                start = mid + 1\n            else:\n                end = mid - 1\n\n        return res\n```\n\n\n```cpp []\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nclass Solution {\npublic:\n    int maxTwoEvents(vector<vector<int>>& events) {\n        sort(events.begin(), events.end(), [](vector<int>& a, vector<int>& b) {\n            return a[1] < b[1];\n        });\n\n        int n = events.size();\n        vector<int> maxValues(n);\n        maxValues[0] = events[0][2];\n\n        for (int i = 1; i < n; ++i) {\n            maxValues[i] = max(maxValues[i - 1], events[i][2]);\n        }\n\n        int maxSum = 0;\n\n        for (int i = 0; i < n; ++i) {\n            int start = events[i][0];\n            int value = events[i][2];\n            int idx = binarySearch(events, start - 1);\n\n            int currentSum = value;\n            if (idx != -1) {\n                currentSum += maxValues[idx];\n            }\n\n            maxSum = max(maxSum, currentSum);\n        }\n\n        return maxSum;\n    }\n\nprivate:\n    int binarySearch(vector<vector<int>>& events, int targetEnd) {\n        int start = 0, end = events.size() - 1, res = -1;\n\n        while (start <= end) {\n            int mid = start + (end - start) / 2;\n            if (events[mid][1] <= targetEnd) {\n                res = mid;\n                start = mid + 1;\n            } else {\n                end = mid - 1;\n            }\n        }\n\n        return res;\n    }\n};\n```\n\n\n```javascript []\nvar maxTwoEvents = function(events) {\n    // Step 1: Sort events by their end times\n    events.sort((a, b) => a[1] - b[1]);\n\n    let n = events.length;\n    let maxValues = new Array(n).fill(0);\n    maxValues[0] = events[0][2]; // Value of the first event\n\n    // Fill the running max array\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    // Step 3: Iterate through the events and use binary search\n    for (let i = 0; i < n; i++) {\n        let start = events[i][0];\n        let value = events[i][2];\n\n        // Find the latest event that ends before the current event starts\n        let idx = binarySearch(events, start - 1);\n\n        let currentSum = value;\n        if (idx !== -1) currentSum += maxValues[idx];\n\n        maxSum = Math.max(maxSum, currentSum);\n    }\n\n    return maxSum;\n};\n\n// Helper: Binary search to find the latest event that ends <= targetEnd\nfunction binarySearch(events, targetEnd) {\n    let start = 0, end = events.length - 1, res = -1;\n\n    while (start <= end) {\n        let mid = Math.floor(start + (end - start) / 2);\n        if (events[mid][1] <= targetEnd) {\n            res = mid;\n            start = mid + 1;\n        } else {\n            end = mid - 1;\n        }\n    }\n\n    return res;\n}\n```\n\n\n```java []\nimport java.util.*;\n\nclass Solution {\n    public int maxTwoEvents(int[][] events) {\n        // Step 1: Sort events by their end times\n        Arrays.sort(events, (a, b) -> Integer.compare(a[1], b[1]));\n\n        int n = events.length;\n        int[] maxValues = new int[n];\n        maxValues[0] = events[0][2]; // Value of the first event\n\n        // Fill the running max array\n        for (int i = 1; i < n; i++) {\n            maxValues[i] = Math.max(maxValues[i - 1], events[i][2]);\n        }\n\n        int maxSum = 0;\n\n        // Step 3: Iterate through the events and use binary search\n        for (int i = 0; i < n; i++) {\n            int start = events[i][0];\n            int value = events[i][2];\n\n            // Find the latest event that ends before the current event starts\n            int idx = binarySearch(events, start - 1);\n\n            int currentSum = value;\n            if (idx != -1) currentSum += maxValues[idx];\n\n            maxSum = Math.max(maxSum, currentSum);\n        }\n\n        return maxSum;\n    }\n\n    // Helper: Binary search to find the latest event that ends <= targetEnd\n    private int binarySearch(int[][] events, int targetEnd) {\n        int start = 0, end = events.length - 1, res = -1;\n\n        while (start <= end) {\n            int mid = start + (end - start) / 2;\n            if (events[mid][1] <= targetEnd) {\n                res = mid;\n                start = mid + 1;\n            } else {\n                end = mid - 1;\n            }\n        }\n\n        return res;\n    }\n}\n```\n\n\n```go []\nimport (\n\t"sort"\n)\n\nfunc maxTwoEvents(events [][]int) int {\n\t// Step 1: Sort events by their end times\n\tsort.Slice(events, func(i, j int) bool {\n\t\treturn events[i][1] < events[j][1]\n\t})\n\n\tn := len(events)\n\tmaxValues := make([]int, n)\n\tmaxValues[0] = events[0][2] // Value of the first event\n\n\t// Fill the running max array\n\tfor i := 1; i < n; i++ {\n\t\tmaxValues[i] = max(maxValues[i-1], events[i][2])\n\t}\n\n\tmaxSum := 0\n\n\t// Step 3: Iterate through the events and use binary search\n\tfor i := 0; i < n; i++ {\n\t\tstart := events[i][0]\n\t\tvalue := events[i][2]\n\n\t\t// Find the latest event that ends before the current event starts\n\t\tidx := binarySearch(events, start-1)\n\n\t\tcurrentSum := value\n\t\tif idx != -1 {\n\t\t\tcurrentSum += maxValues[idx]\n\t\t}\n\n\t\tmaxSum = max(maxSum, currentSum)\n\t}\n\n\treturn maxSum\n}\n\n// Helper: Binary search to find the latest event that ends <= targetEnd\nfunc binarySearch(events [][]int, targetEnd int) int {\n\tstart, end, res := 0, len(events)-1, -1\n\n\tfor start <= end {\n\t\tmid := start + (end-start)/2\n\t\tif events[mid][1] <= targetEnd {\n\t\t\tres = mid\n\t\t\tstart = mid + 1\n\t\t} else {\n\t\t\tend = mid - 1\n\t\t}\n\t}\n\n\treturn res\n}\n\n// Utility: Max function\nfunc max(a, b int) int {\n\tif a > b {\n\t\treturn a\n\t}\n\treturn b\n}\n```\n\n\n---\n\n![image.png](https://assets.leetcode.com/users/images/d81a7cee-fa73-41a2-82dc-65bf475d960c_1722267693.3902693.png) {:style=\'width:250px\'}
['Array', 'Binary Search', 'C', 'Sorting', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'Dart']